[Java] BOJ 18870: 좌표 압축과 랭킹 알고리즘

---

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

---

이해하기

좌표 압축을 적용한 값 X'i가  Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같다. 중복되는 원소가 같은 순위를 가진다는 점이 마치 SQL Server에서의 DENSE_RANK 느낌인데, 이 문제에서 추가로 고려할 점은 값이 작을수록 순위가 높다는 것과 가장 높은 순위는 0순위라는 점이다.

 

1. 중복되는 원소를 같은 순위로 둔다는 점을 고려할 때, 일단 Set이나 Map을 활용하면 좋을 듯하다.
2. 값이 작을수록 높은 순위를 갖는다는 것은, 오름차순 정렬을 기준으로 첫 인덱스에 해당하는 원소가 가장 높은 순위를 갖는다는 것이다. 가장 높은 순위가 0순위임도 인지하자.

---

풀이

압축된 좌표를 key로 두고 해당 순위를 value로 하자. 그러면 key로 value 값을 찾아 출력하기만 하면 되는 간단한 문제다. 따라서 HashMap이 적절할 듯하다.

public class Problem18870 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] origin = new int[N];
        int[] ascending = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            origin[i] = ascending[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(ascending);

        HashMap<Integer, Integer> ranking = new HashMap<>();
        int rank = 0;

        for (int num : ascending) {
            if (!ranking.containsKey(num)) {
                ranking.put(num, rank++);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int key : origin) {
            int value = ranking.get(key);
            sb.append(value).append(" ");
        }

        System.out.println(sb.toString().trim());
    }
}

        int rank = 0;

        for (int num : ascending) {
            if (!ranking.containsKey(num)) {
                ranking.put(num, rank++);
            }
        }

*일반 for문을 사용하지 않고 향상된 for문을 사용한 이유는, rank가 중복되지 않은 값이 들어올 때만 증가해야 하기 때문이다.

---

마무리

좌표 압축 알고리즘은 세그먼트 트리 파트에서 은근히 자주 쓰인다고 한다. 지금 개념을 잘 익혀서 향후 응용, 확장할 수 있도록 신경 써야겠다.