[백준] 18870 : 좌표 압축 JAVA 풀이

N개의 숫자 중 자신보다 작은 숫자의 개수를 세고 출력하기만 하면 되나....했지만

잘보면 처음 입력되는 숫자 N개의 순서대로 출력해야 한다는 점이 좀 까다로웠다.

 

N개의 숫자를 배열 arr에 저장하고,

arr에서 중복되는 값을 제외하고 그걸 정렬한 값을 담은 새로운 배열 tmp를 만든 뒤에

두 배열의 값을 비교하면서 일치할 때마다 tmp의 인덱스(자기보다 작은 수의 개수)를 출력하려고 했지만

예상대로 시간초과가 됐다.

 

이걸 어쩌나 고민하던 중 해쉬맵을 알게 됐다.

해쉬맵은 키값과 데이터로 이루어져서 키값은 중복될 수 없지만 데이터는 중복될 수 있다.

이를 이용해서 다음과 같은 순서로 코드를 짰다.

 

1. arr라는 배열에 N개의 숫자를 저장한다.

2. tmp라는 배열에 arr배열을 복사해둔다. (처음 입력되는 숫자 N개의 순서대로 출력해야 하기 때문)

3. arr배열을 정렬한다.

4. hmap이라는 해쉬맵을 생성한다.

5. Xi > Xj를 만족하는 수의 개수를 셀 변수 cnt를 생성하고 0으로 초기화한다.

6. arr의 길이만큼 반복하며 arr배열 중 hmap에 없는 값은 키값으로, cnt를 데이터로 추가한 뒤 cnt를 증가시킨다.

7. hmap에서 tmp배열(처음 입력된 배열)에 저장된 값을 키로 갖는 데이터를 출력한다.

 

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.HashMap;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int[] tmp = arr.clone();
        
        Arrays.sort(arr);
        HashMap<Integer, Integer> hmap = new HashMap<>();
        int cnt = 0;
        
        for(int i=0;i<N;i++){
            if(!hmap.containsKey(arr[i])){
                hmap.put(arr[i], cnt);
                cnt++;
            }
        }
        for(int i=0;i<N;i++){
            sb.append(hmap.get(tmp[i])).append(" ");
        }
        System.out.print(sb);
    }
}