[바미] 좌표 압축

문제

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

 

코드 

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

// 좌표를 값과 원래 인덱스로 매핑
const indexedCoordinates = coordinates.map((value, index) => ({ value, index }));

// 값에 따라 정렬
indexedCoordinates.sort((a, b) => a.value - b.value);

// 압축 좌표를 저장할 배열
const compressed = new Array(N);

// 좌표 압축 실행
let rank = 0;
for (let i = 0; i < N; i++) {
    // 동일한 좌표가 이전 좌표와 다르면 순위 증가
    if (i > 0 && indexedCoordinates[i].value !== indexedCoordinates[i - 1].value) {
        rank++;
    }
    // 원래 인덱스 위치에 순위 저장
    compressed[indexedCoordinates[i].index] = rank;
}

// 결과 출력
console.log(compressed.join(' '));

코드 설명

const N = parseInt(input[0], 10);
const coordinates = input[1].split(' ').map(Number);

먼저 입력 데이터를 읽어온 후, 첫 번째 줄에서 N(좌표의 수)을 추출한 뒤, 공백으로 구분된 좌표들을 읽어 숫자 배열로 변환해줍니다.

const indexedCoordinates = coordinates.map((value, index) => ({ value, index }));

그 후 각 좌표값과 그 원래의 인덱스를 객체로 매핑해줍니다. 이렇게 해야 좌표를 정렬할 때 원래의 인덱스 정보를 유지할 수 있습니다.

 

indexedCoordinates.sort((a, b) => a.value - b.value);

이후 매핑된 객체 배열을 값에 따라 오름차순으로 정렬해줍니다.

코드 동작은 반복문을 돌면서 같은 값을 가진 좌표에는 같은 순위를 부여하고, 다른 값이 나타나면 순위를 증가시키는 형태입니다.

 

// 압축 좌표를 저장할 배열
const compressed = new Array(N);

// 좌표 압축 실행
let rank = 0;
for (let i = 0; i < N; i++) {
    // 동일한 좌표가 이전 좌표와 다르면 순위 증가
    if (i > 0 && indexedCoordinates[i].value !== indexedCoordinates[i - 1].value) {
        rank++;
    }
    // 원래 인덱스 위치에 순위 저장
    compressed[indexedCoordinates[i].index] = rank;
}

 

이제 compressed라는 배열을 초기화하는데 이 때 좌표의 수 N만큼의 길이를 갖는 배열이 됩니다.

그 후 rank라는 변수를 0으로 초기화해주는데 이 rank는 각 유니크한 좌표에 대해 새롭게 압축된 값을 추적하는 데 사용되는 변수입니다.

 

그 이후 for (let i = 0; i < N; i++) { ... } 부분이 진행되는데 이 반복문은 값에 따라 정렬된 좌표 배열을 순회하면서 각 좌표에 압축된 값을 할당하는 역할을 하는 반복문입니다.

 

그 안을 보죠.

 

    if (i > 0 && indexedCoordinates[i].value !== indexedCoordinates[i - 1].value) {
        rank++;
    }

제일 처음 만나는 조건문에서 현재 좌표(indexedCoordinates[i].value)가 이전 좌표(indexedCoordinates[i - 1].value)와 다르면 순위를 증가시킵니다.

 

그러니까 첫 번째 요소가 아닐 때만(i > 0) 이 조건을 검사하는 것인데 더 높은 유니크 값이 정렬된 목록에서 발견될 때 새로운 순위를 할당 해주는 것을 의미합니다.

 

그 후

compressed[indexedCoordinates[i].index] = rank;

에서 현재의 rank를 원래 좌표가 있던 위치(indexedCoordinates[i].index)에 compressed 배열에 저장합니다.

 

좌표가 정렬된 순서로 처리되더라도 압축된 값들이 원래 제공된 순서대로 저장되도록 보장해주는 것이죠.

 

이 과정이 끝나면 

console.log(compressed.join(' '))

압축된 좌표 배열을 공백으로 구분하여 문자열로 만들어 출력해줍니다.

문제 해설

오늘 문제에서 풀어본 기법은 좌표 압축은 많은 알고리즘 문제에서 유용하게 사용되는 기법입니다. 

특히, 값의 범위가 넓거나 특정 알고리즘이 정수 인덱스를 요구하는 경우에 좌표 압축이 유용하죠.

 

좌표 압축은 각 좌표 값을 그 좌표보다 작은 서로 다른 좌표들의 개수로 대체하는 과정을 의미하는데 좌표의 상대적인 순서는 유지되면서 값의 범위는 줄어들게 되죠.

 

예를 들어볼게요. 주어진 좌표가 아래와 같을경우

-10, 2, 4

이 좌표를 압축하게 될 때 아래의 값이 됩니다.

0, 1, 2

 

시간 복잡도

이 알고리즘의 시간 복잡도는 주로 정렬 과정에서 결정되기 때문에 0(N log N)의 시간의 복잡도를 갖습니다.

이 때  N은 좌표의 개수를 의미하며, log N은 분할 과정에서 발생하는 각 단계의 비교 횟수를 나타냅니다.

공간 복잡도

 이 문제에서는 입력 데이터와 같은 크기의 추가 배열이 필요합니다. 

입력받은 좌표 데이터를 저장하는 데 N만큼의 공간이 필요하고, 좌표 압축 과정에서 각 좌표의 새로운 순위를 저장하기 위한 배열도 N만큼의 공간을 차지하기 때문에 0(N)의 공간 복잡도를 가집니다.