알고리즘 :: 손에 손잡고, 더블 정렬 [함수 개선?]

알고리즘 :: 손에 손잡고, 더블 정렬 [함수 개선?]

알고리즘 공부하며 배운내용

손에 손잡고

올림픽 개막식에 손에 손잡고 공연을 한다.

우선 모든 사람이 옆 사람과 손을 잡을 수 있는지 확인을 하고,

모두와 잡을 수 있으면 얼마나 떨어져 있는지 알아내려고 한다.

각 사람의 위치는 (x, y) 좌표로 표현된다.

y 좌표가 같으면 같은 줄에 서있는 거다.

들어오는 값

첫 번째 줄에는 전체 사람 수 N이 입력된다.

두 번째 줄부터는 사람들 차례대로(x, y)가 입력된다.

예)

5

1 3

2 3

3 5

1 5

7 5

보여줄 값

모두가 옆 사람과 손을 잡을 수 있는 경우

SUCCESS 출력, 그 다음줄에 가장 먼 거리를 출력

아니면 FAIL 출력

예)

SUCCESS

4

핵심 포인트

전부 다 비교하지 않고, 왼쪽 오른쪽만 비교하면 된다.

y좌표가 같으면 x좌표를 비교해서 오름차순으로 정렬하고, 다르면 y좌표 오름차순으로 정렬을 한다.

그럼 딱 왼쪽 오른쪽만 비교하면 된다.

코드

정렬 뒤에 함수 부분에서 코드를 좀 더 다듬을 수 있을 것 같지만,

우선 앞으로 전진! 다음에 돌아올지도

// VSCode에서 JavaScript 테스트 하기위한 코드 // 메모장에 테스트 케이스 넣고 stairs.txt로 저장했다. let fs = require('fs') let input = fs.readFileSync('handhand.txt').toString().split('

') // 배열의 첫 번째는 사람수라 빼간다 const ppl = +input.shift() let coorArr = [] let sameLine = 0 let tempDist = 0 let distance = 0 // 여기가 포인트 // y좌표 같으면 x좌표 오름차순, 다르면 y좌표 오름차순 coorArr = input.sort((a, b) => { if(a[2] === b[2]) { return a[0] - b[0] } else { return a[2] - b[2] } }) // 왼쪽 오른쪽 비교해서 출력하는 함수 function showDist(coor) { for(let i = 0; i < coor.length-1; i++) { if(sameLine === 0 && coor[i][2] !== coor[i+1][2]) { return 'FAIL' } if(coor[i][2] === coor[i+1][2]) { sameLine = 1 tempDist = +coor[i+1][0] - +coor[i][0] distance = Math.max(+distance, +tempDist) } else { sameLine = 0 continue; } } return `SUCCESS

${distance}` } console.log(showDist(coorArr));

from http://forgottenknowledge.tistory.com/127 by ccl(A) rewrite - 2021-09-24 21:01:35