[Baekjoon] 18870 좌표 압축 - JAVA

문제

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

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

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

---

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

---

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

---

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

---

예제 입력 1 

5
2 4 -10 4 -9

예제 출력 1 

2 3 0 3 1

예제 입력 2 

6
1000 999 1000 999 1000 999

예제 출력 2 

1 0 1 0 1 0

 

---

📝 제출 답안

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] origin = new int[n];
        int[] sorted = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            origin[i] = Integer.parseInt(st.nextToken());
            sorted[i] = origin[i];
        }
        Arrays.sort(sorted);

        HashMap<Integer, Integer> rank = new HashMap<>();
        int ranking = 0;
        for (int i = 0; i < n; i++) {
            if (!rank.containsKey(sorted[i])) {
                rank.put(sorted[i], ranking);
                ranking++;
            }
        }

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

        bw.write(sb.toString());
        bw.flush();
    }
}

 

 

이 문제는 좌표 압축을 해결하는 것이었는데, 좌표 압축이 무엇인지부터 이해해야 했다.

 

좌표 압축은 데이터를 간결하게 표현하기 위해 각 값의 상대적 순위를 계산하는 기법이다. 이 방법은 값의 범위가 매우 크거나 불연속적인 경우에 유용하다.

쉽게 말해서 주어진 숫자 배열에서 각 숫자를 오름차순으로 정렬했을 때의 순위를 말하는 것이다.

 

 

입출력 처리

입출력 처리는 BufferedReader, StringTokenizer와 Bufferwriter를 사용해 시간을 단축했다.

 

 

배열 선언 및 정렬

이 문제를 해결하기 위해서는

입력 받은 순서 그대로 값을 저장할 배열 origin과

origin 배열을 정렬하여 저장할 배열 sorted를 선언해준다.

 

각 배열에 입력된 숫자들을 저장한 뒤 sorted 배열을 오름차순으로 정렬해준다.

 

 

HashMap을 사용한 좌표 압축

HashMap을 사용해서 각 값에 대해 압축된 순위를 저장한다.

sorted 배열을 순회하면서 값이 rank에 존재하지 않으면 현재 ranking 값을 매핑하고, raking 값을 1 증가시킨다.

이렇게 하면 중복된 값은 같은 순위를 가지므로 중복을 제거하면서 순위를 할당할 수 있다.

HashMap<Integer, Integer> rank = new HashMap<>();
int ranking = 0;
for (int i = 0; i < n; i++) {
    if (!rank.containsKey(sorted[i])) {
        rank.put(sorted[i], ranking);
        ranking++;
    }
}

 

 

결과 조합하기

마지막으로 origin 배열을 순휘하면서 각 숫자에 해당하는 순위를 rank에서 찾아 StringBuilder에 문자열을 추가해주면

순서에 맞는 순위값을 출력할 수 있다.

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

 

 

제출 현황