[바미] 좌표 정렬하기

문제

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

11650번: 좌표 정렬하기

코드

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});
}

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

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

console.log(result.trim());

코드 설명

먼저 각 줄에서 split(' ')를 사용하여 공백을 기준으로 문자열을 분리하고, map(Number)를 통해 문자열을 숫자로 변환해줍니다.(이렇게 변환된 숫자들이 x와 y 좌표입니다.)

그 후 각 좌표를 객체 {x, y} 형태로 배열 points에 저장해줍니다.

 

points.sort((a, b) => { ... })에서 sort()로 배열을 정렬할 때 두 객체 a와 b의 x좌표를 먼저 비교하고, x좌표가 같을 경우 y좌표를 비교하여 정렬해줍니다.

a.x === b.x인 경우 a.y - b.y를 반환하여 y좌표에 따라 정렬하고, 그렇지 않으면 a.x - b.x를 반환하여 x좌표에 따라 정렬합니다.

 

출력하기 전에 result 문자열을 생성해줍니다. forEach를 사용하여 정렬된 각 점의 x좌표와 y좌표를 문자열에 추가하여 각 좌표는 ${point.x} ${point.y}\n 형태로 result에 추가되며, 마지막에는 trim()을 호출하여 결과 문자열의 끝에 있는 불필요한 줄바꿈을 제거해주었습니다.

문제 해설

이 문제에서는 2차원 평면 위에 주어진 점들을 특정한 순서로 정렬해야 합니다.

저는 주어진 2차원 평면 위의 점들을 x좌표가 증가하는 순서로 정렬하고, 만약 두 점의 x좌표가 동일하다면 그 점들을 y좌표가 증가하는 순서로 추가로 정렬하여 이 문제를 해결하였습니다.

 

이러한 문제 역시 JS의 기본 내장 함수로 해결 할 수 있고, 저는 Array.prototype.sort()을 사용하여 배열의 요소들을 정렬하였습니다.

points.sort((a, b) => {
    if (a.x === b.x) {
        return a.y - b.y;  // x좌표가 같을 경우 y좌표로 정렬
    }
    return a.x - b.x;    // x좌표로 정렬
});

 

중 (a, b) => {}부분에서 비교함수를 정의하는데 이 비교 함수는 두 요소 a와 b를 받고, 비교하여 그 결과에 따라 정렬 순서를 결정하는 데 사용하고 있습니다.

 

그 결과의 형태는 아래와 같습니다.

• 함수가 반환하는 값이 0보다 작다면, a를 b보다 앞에 위치시킨다. (즉, a가 더 작다.)
• 함수가 반환하는 값이 0이면, a와 b의 순서를 변경하지 않는다.
• 함수가 반환하는 값이 0보다 크다면, b를 a보다 앞에 위치시킨다. (즉, b가 더 작다.)

그 이후 points.sort((a, b) => {}) 안에서 x좌표와 y좌표에 따라 조건에 따라 아래의 형태로 동작하게 됩니다.

• x좌표가 같을 경우 : y좌표에 따라 오름차순으로 정렬한다.
• x좌표가 다를 경우 : x좌표에 따라 오름차순으로 정렬한다.

이렇게 되면 입력된 점들이 다음과 같다고 가정했을 때

[(3, 4), (1, 1), (1, -1), (2, 2), (3, 3)]

위 정렬 로직에 따라 아래와 같이 배열이 정렬됩니다.

[(1, -1), (1, 1), (2, 2), (3, 3), (3, 4)]

 

시간 복잡도

O(N log N)을 가지게 되는데 sort() 함수가 가장 큰 영향을 미칩니다. 

이 문제외에 다른 정렬 알고리즘 문제들을 보셔서 아시겠지만 O(N log N)은 흔한 정렬 알고리즘에서 가지는 시간 복잡도입니다.

 

여기서 N은 점의 개수를 말하는데 점의 개수 N이 증가함에 따라 필요한 작업량은 N log N에 비례하여 증가합니다.

이 뜻은 정렬을 수행할 때 각 항목을 적절한 위치로 이동시키기 위해 비교하고, 교환하는 작업이 그 만큼 더 많이 필요하다는 것을 의미하는 것입니다.

공간 복잡도

O(N)을 가지게 됩니다.

여기서 N은 배열에 저장된 점의 개수를 나타냅니다. 이 공간은 입력받은 점들을 저장하기 위해 사용됩니다.

 

추가적으로 정렬된 데이터를 출력하기 위한 문자열을 생성할 때 이 문자열을 구성하기 위한 추가적인 메모리가 필요합니다.

각 점의 데이터를 문자열로 변환하여 결과를 출력하는 데 사용되는 공간도 고려될 수 있습니다.

그러나 이 공간은 결과를 출력하는 순간에만 필요하므로, 주로 점을 저장하는 데 필요한 공간이 전체 공간 복잡도를 차지하게 됩니다.