BOJ18870 좌표 압축

https://www.acmicpc.net/problem/18870 (opens new window)

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력한다.

좌표 압축?

좌표 압축에는 특정한 성질을 찾을 수 있었다. 전체 좌표에서 자신 보다 작은 좌표의 개수가 즉 압축된 자신의 index로 표현된다.

2 4 -10 4 -9
2 3 0 3 1

문제 접근은 단순하다. 자신 보다 작은 좌표를 찾아 count하기만 하면 된다. 하지만 N의 크기는 최대 1,000,000에 가깝다. 만약 시간 복잡도가 O(N^2)보다 작아야 문제 해결이 가능하다.

그래서 이때 정렬 알고리즘이 사용된다. Java 내부에 정의된 정렬 메소드는 최대 O(NlogN)임을 보장하기 때문에 적용이 가능하다.

제출 코드

원본 배열의 훼손을 막기 위해 깊은 복사를 진행하여 정렬을 진행한다.

int[] copyNums = nums.clone(); // 깊은 복사
Arrays.sort(copyNums); // 오름차순 정렬

이제 map을 사용하여 오름차순 정렬된 배열에서 값을 하나씩 꺼내가며 만약 num값이 있지 않은 경우 새롭게 등장한 값이기 때문에 추가한 후 count해준다.

Map<Integer, Integer> map = new HashMap<>();
int count = 0;
for (int num : copyNums) {
    if (!map.containsKey(num)) {
        map.put(num, count++);
    }
}

아래는 최종 제출 코드이다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class BOJ18870 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        int[] copyNums = nums.clone(); // 깊은 복사
        Arrays.sort(copyNums); // 오름차순 정렬

        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (int num : copyNums) {
            if (!map.containsKey(num)) {
                map.put(num, count++);
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (int num : nums) {
            stringBuilder.append(map.get(num)).append(" ");
        }
        System.out.println(stringBuilder);
    }
}

#algorithm #BOJ #정렬 #값 / 좌표 압축