[바미] 좌표 정렬하기 2

문제

https://www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = parseInt(input[0], 10);
const points = [];

for (let i = 1; i <= N; i++) {
    const [x, y] = input[i].split(' ').map(Number);
    points.push({x, y});
}

// 정렬: y좌표에 따라 오름차순 정렬하고, y좌표가 같다면 x좌표로 정렬
points.sort((a, b) => {
    if (a.y === b.y) {
        return a.x - b.x;  // y좌표가 같을 경우 x좌표로 정렬
    }
    return a.y - b.y;    // y좌표로 정렬
});

// 결과 출력
let result = '';
points.forEach(point => {
    result += `${point.x} ${point.y}\n`;
});

console.log(result.trim());

코드 설명

데이터를 입력 받은 후 points.sort((a, b) => {...}) 부분에서 각 점의 좌표를 객체 형태로 저장된 points데이터를 sort() 메서드와 비교 함수를 사용하여 정렬을 해줍니다.

 

그 후 정렬 기준에 맞춰 각 점을 정렬해 주는데 정렬 규칙은 아래와 같습니다.

• y좌표가 동일하지 않은 경우 -모든 점들을 먼저 y좌표에 따라 오름차순으로 정렬.
• y좌표가 동일한 경우 - x좌표에 따라 오름차순으로 정렬.

그 이후 정렬이 완료되면 forEach 루프를 사용하여 정렬된 각 점의 좌표를 문자열 형태로 result에 추가 후 trim()으로 출력 해줍니다.

문제 해설

이 문제는 어떻게 2차원 평면에 있는 점들을 특정 순서대로 정렬해 줄 것인가?가 관건입니다.

자세한 문제 설명은 코드 설명에 적혀 있으므로 코드 설명부분을 참고하시면 될 거 같습니다.

이와 같은 코드 패턴은  2차원 평면상의 데이터를 다룰 때 자주 사용되는 방식입니다.

 

시간 복잡도 

sort() 함수를 사용했기 때문에 평균적으로 O(N log N)의 시간 복잡도를 가지게 됩니다.

여기서 N은 정렬해야 할 데이터의 개수를 의미하고, log N은 데이터를 분할하며 정렬하는 과정에서 발생하는 비교 횟수를 의미합니다.

공간 복잡도

이 문제에서는 점들의 좌표를 객체 배열로 관리하므로, 입력된 점의 개수 N에 비례하는 공간이 필요하고, 최종 결과를 출력하기 위해 생성되는 문자열 역시 N개의 정보를 모두 포함해야 하므로 0(N)의 공간을 차지하게됩니다.