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

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

 

 

손에 손잡고

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

 

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

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

 

각 사람의 위치는 (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 테스트 하기위한 코드
// 메모장에 테스트 케이스 넣고 handhand.txt로 저장했다.
let fs = require('fs')
let input = fs.readFileSync('handhand.txt').toString().split('\n')

// 배열의 첫 번째는 사람수라 빼간다
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 \n${distance}`
}

console.log(showDist(coorArr));