[18870 - JAVA] 좌표 압축

 

문제

 

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

 

예제 입력 

 

5

2 4 -10 4 -9

 

예제 출력 

 

2 3 0 3 1

 

문제 힌트

 

5개 숫자 중 2보다 작은 개수 4보다 작은 개수 -10보다 작은 개수....

 

처음 풀이

import java.io.*;
import java.util.*;

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] x = new int[n];
        TreeSet<Integer> hashset = new TreeSet<>();
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            x[i] = num;
            hashset.add(num);
        }

        System.out.println(hashset);
        
        for (int i = 0; i < n; i++) {
            int num = x[i];
            int count = hashset.headSet(num).size();
            sb.append(count).append(" ");
        }
        
        System.out.print(sb.toString());
    }
}

 

이 문제에서 중요한 부분이 정렬과 중복 체크라고 생각했고 TreeSet의 경우 정렬과 중복 제거를 제공하기 때문에 사용하였다. 그러나 하단 반복문에서 hashSet의 큰 문제가 발생해 시간초과가 발생한다. 예제 같이 짧은 경우 모든 배열을 탐색하는데 오랜시간이 걸리지 않지만 배열의 크기가 커질 수 록 탐색 시간이 오래걸린다.

 

두번째 풀이

 

import java.io.*;
import java.util.*;

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> hashmap = new HashMap();
        int[] x = new int[n];
        int[] sortList = new int[n];
        int count = 0;
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(st.nextToken());
            sortList[i] = x[i];
        }

        Arrays.sort(sortList);

        for (int sortnum : sortList) {
            if (!hashmap.containsKey(sortnum)) {
                hashmap.put(sortnum, count);
                count++;
            }
        }
        
        for (int key : x) {
            sb.append(hashmap.get(key)).append(" ");
        }

        System.out.println(sb);
    }
}

 

HashMap으로 값을 카운팅하는 방식으로 처리해 키값으로 count한 값을 출력하는 방식