[JAVA] 백준 (실버2) 18870번 좌표 압축

링크

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

---

문제 설명

정답률 39.529%

수직선 위에 N개의 좌표 $X_1, X_2, ..., X_N$이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

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

$X_1, X_2, ..., X_N$에 좌표 압축을 적용한 결과 $X'_1, X'_2, ..., X'_N$를 출력해보자.

---

입력 예제

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 $X_1, X_2, ..., X_N$이 주어진다.

5
2 4 -10 4 -9

---

출력 예제

첫째 줄에 $X'_1, X'_2, ..., X'_N$을 공백 한 칸으로 구분해서 출력한다.

2 3 0 3 1

---

제한

• $1 ≤ N ≤ 1,000,000$
• ${-10}^9 ≤ X_i ≤ 10^9$

---

풀이

우선 문제를 이해해보면 2, 4, -10, 4, -9가 주어졌을 때 순서대로 좌표 압축을 적용하면 다음과 같다.

• 2보다 작은 수는 -10, -9로 2개
• 4보다 작은 수는 2, -10, -9로 3개
• -10보다 작은 수는 없으므로 0개
• 4는 앞에 4와 동일하게 3개
• -9보다 작은 수는 -10으로 1개

따라서 결과는 2, 3, 0, 3, 1이 된다. 작은 수를 카운트할 때 중복된 수는 카운트 하지 않는다.

단순히 모든 원소에 대해서 비교하면 쉽겠지만 N의 크기는 1,000,000으로 이중 for문을 사용할 경우 최악의 경우 시간 초과가 발생한다. 그래서 일일이 카운트하는게 아니라 각 원소의 순위를 매기는 방법을 사용한다.

2, 4, -10, 4, -9를 작은 수를 높은 순위로 매기면 결과는 2, 3, 0, 3, 1이 되고 앞에서 카운트했을 때와 동일한 결과가 나온다.

중복된 수들은 동일한 순위를 가지므로 HashMap을 사용하여 key는 좌표, value는 순위로 작은 수부터 순위를 매겨나간다.

int[] sorted = origin.clone(); 
Arrays.sort(sorted);  //오름차순으로 정렬

int rank = 0;
for (int key : sorted) {
	//이미 순위를 매긴 원소는 pass
    if (!map.containsKey(key)) {
        map.put(key, rank);
        rank++;
    }
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] origin = new int[N];  //원본 배열
        HashMap<Integer, Integer> map = new HashMap<>();

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

        int[] sorted = origin.clone();  //깊은 복사
        Arrays.sort(sorted);

        int rank = 0;
        for (int key : sorted) {
            if (!map.containsKey(key)) {
                map.put(key, rank);
                rank++;
            }
        }

        StringBuilder sb = new StringBuilder();
		//정렬되지 않은 원본 배열 순으로 순위를 저장
        for (int key : origin) {
            sb.append(map.get(key)).append(" ");
        }

        System.out.println(sb);
    }
}