백준 18870 좌표 압축

문제

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

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

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

---

코드

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

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());
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        int[] array=new int[n];
        String s=br.readLine();
        StringTokenizer st=new StringTokenizer(s);
        for(int i=0; i<n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
            pq.add(array[i]);
        }

        int[] sorted=new int[n];
        int previous=pq.remove();
        sorted[0]=previous;
        int index=1;
        for(int i=1; i<n; i++){
            int temp=pq.remove();
            if(previous==temp)
                continue;
            else
                sorted[index++]=temp;
            previous=temp;
        }

        for(int i=0; i<n; i++)
            bw.write(Arrays.binarySearch(sorted, 0, index, array[i])+" ");

        bw.flush();
    }
}

---

해결 과정

1. Counting Sort를 사용하면 좋겠지만 수의 범위가 약 20억이라서 Scanner로 처음의 배열을 만들고 Heap Sort를 사용해서 중복된 수는 제거하면서 새로운 정렬된 배열을 만들어준 뒤에, 처음의 배열에서 각각의 요소를 정렬된 새 배열에서 Binary Search 했다. 그 인덱스가 정답이기 때문에 바로 출력해줬다.

2. 시간 초과(혹시나 싶어서 Scanner 대신 BufferedReader, BufferedWriter로 바꿨다)

3. 😁