[BOJ] 18870: 좌표 압축(JAVA)

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

18870번: 좌표 압축

문제

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

Xi를 좌표 압축한 결과 X'i의 값은 Xi > 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

 

---

[문제 풀이]

1. int[] num - 입력 받은 좌표 

2. int[] clone - num배열의 clone, 오름차순 정렬

3. HashMap<Integer, Integer> map - <정렬된 좌표값, 순위> 저장

    3-1. clone 배열에는 입력받은 N개의 좌표를 Arrays.sort(clone); 을 이용하여 오름차순 정렬한 값들이 저장되어있다.

    3-2. clone 배열을 원소를 순차적으로 탐색하고 map에 이미 존재하는 값은 넣지 않는다. 따라서 map의 key는 작은 값 순서대로 값이 들어갈 것이고, value의 rank도 순차적으로 증가할 것이다. 

4. 처음 입력 받은 좌표 num배열의 원소값을 key값으로 map에서 value를 검색하여 출력한다.

 

[코드]

import java.util.*;

public class Main {

    public static void main(String[] args) {
    
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      StringBuilder sb = new StringBuilder();
      int[] num = new int[N];
  
      
      for(int i=0;i<N;i++) {
             int x = sc.nextInt();
             num[i] = x;
      }
      int[] clone = num.clone();
      Arrays.sort(clone);
      HashMap<Integer, Integer> map = new HashMap<>();
      int rank=0;
      for(int n:clone) {
            if(!map.containsKey(n)) {
                  map.put(n,rank++);
             }
      }
      for(int i=0;i<N;i++) {
             sb.append(map.get(num[i])).append(' ');
      }
      System.out.println(sb.toString());
    }
}