[백준] 18870_좌표압축

 

Sliver

 

문제 

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

 

---

풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);     
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();
        int[] arr = new int[N];
        for(int i =0; i< N ; i++){
            int num = sc.nextInt();
            arr[i] = num;
        }
        int[] sorted = arr.clone();
        Arrays.sort(sorted);
        Map<Integer, Integer> map = new HashMap<>();
        int index = 0;
        for(int i =0; i< N ; i++){
            if(!map.containsKey(sorted[i]))
                map.put(sorted[i], index++);
        }
        
        for(int i =0; i< N ; i++){
            sb.append(map.get(arr[i])).append(" ");
        }
        
        System.out.println(sb);
        
        sc.close();
    }
    
}

 

 

해결방법 

좌표별 압축 후의 좌표의 데이터를 저장하기 위해 Map을 사용했다. 

Key로는 압축 전 좌표를, value로는 압축 후 좌표를 저장해 주었다. 

Map 자료구조를 사용한 이유는 key를 통해 value를 빠르게 가져올 수 있고, conatainsKey 메서드를 사용해 key의 중복값을 처리할 수 있기 때문이다. 

 

 

 

---

 

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