[백준] Q18870 좌표압축 JAVA

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

18870번: 좌표 압축

난이도 Silver III

 

문제 이해

수직선 위 N개의 좌표가 있다.

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

 

접근 방법 및 예제의 이해

소팅을 통한 접근을 생각. 예제를 통해 이해하자면

2 4 -10 4 -9  >> -10 -9 2 4 4

0 1 2 3 3 >> 2 3 0 3 1

소팅과 Map을 이용하여 구현하려고 하였다.

정렬 O(NlogN) 배열 보면서 넣어주기 O(N) 정도로 생각하였음.

 

제한조건

N의 범위가 $10^6$, $X_i$의 범위가 int형 범위안에 들어가기 때문에 int로 처리하여도 가능하다.

 

import java.io.*;
import java.util.*;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        int[] data = new int[N];
        for(int i =0;i<N;i++){
            data[i] = Integer.parseInt(st.nextToken());
           pq.add(data[i]);
        }
        Map<Integer,Integer> ref = new HashMap<Integer,Integer>();
        int prev = Integer.MAX_VALUE;
        int cnt =0;
        while(!pq.isEmpty()){
            int cur = pq.poll();
            if(cur != prev){
                ref.put(cur,cnt);
                prev = cur;
                cnt++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i =0;i<N;i++){
            sb.append(ref.get(data[i])).append(" ");
        }
        System.out.print(sb.toString());
    }
}

 

문제점

문제 난이도가 Silver II 로 높지 않지만 글을 올리게 된 건 조금 더 나아진 속도를 생각하기 위해서이다.

실제로 나보다 빠른 방법들을 보게되면 깊은 복사를 통한 새로운 배열 생성 O(N) 

라이브러리를 통한 quick sort O(NlogN)을 통해 구현하였고 

나의 경우 힙 삽입 O(NlogN) 탐색 O(N) 을 통한 힙정렬이였다.

여기서도 역시 힙 정렬보다는 퀵 정렬이 빨랐다.

그래서 이 문제의 경우는 quick sort를 사용하여 푸는 것이 더욱 빠를 것 같다.

 

다른 풀이 또한 보면서 더 나은 점을 찾도록 하자.