[Java] 백준 18870번 : 좌표 압축

문제

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

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

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

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 1

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

예제 입력 2

6
1000 999 1000 999 1000 999

예제 출력 2

1 0 1 0 1 0

 

소스코드

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

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N;
	private static int [] nums, sortNums;
	private static HashMap<Integer, Integer> hm=new HashMap<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(bf.readLine());
		nums=new int[N];
		sortNums=new int[N];
		
		st=new StringTokenizer(bf.readLine());
		for(int i=0;i<N;i++) {
			sortNums[i]=nums[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(sortNums);
		
		int rank=0;
		for(int i=0;i<N;i++) {
			if(!hm.containsKey(sortNums[i])) {
				hm.put(sortNums[i], rank++);
			}
		}
		
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<N;i++) {
			sb.append(hm.get(nums[i])).append(' ');
		}
		
		System.out.println(sb);
	}

}

시간 초과로 인해 애를 먹었던 문제입니다. 

1. HashMap 사용

2. List 대신 배열 사용

3. BufferedReader + StringBuilder 사용

 

위 3가지 방법을 통해 시간 초과를 해결하였습니다.

1. 처음에는 list와 indexOf를 이용하여 좌표 압축 결과를 구하고자 하였는데, indexOf가 O(N^2)의 시간복잡도를 가져서 매우 비효율적이라는 것을 알게 되었습니다. HashMap을 사용하면 찾는 rank를 바로 매칭할 수 있기 때문에 이러한 시간복잡도를 줄일 수 있습니다.

2. 데이터 탐색 시에 List는 O(n), 배열은 O(1)의 시간복잡도를 가지므로, 배열을 사용하는 것이 훨씬 효율적입니다.

3. StringBuilder를 사용하지 않고 System.out으로 rank를 하나씩 출력했을 때는 시간 초과를 얻었으나, StringBuilder로 결과값을 모두 모은 후 한번에 출력했더니 시간 초과가 해결되었습니다.