[백준/java] 백준 18870번: 좌표 압축

백준 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) 출력할 때 반드시 System.out.print 함수를 쓰면 무조건 시간초과가 난다. 반드시 StringBuilder나 BufferedWriter를 사용해야한다.

(2) 원래 배열을 복사할 배열을 준비한다. (copy = arr.clone();)

(3) copy 배열을 정렬하고 Map을 이용하여 idx 값을 넣어준다.

 

package sort;

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

public class LocationPress {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < arr.length; i++) arr[i] = Integer.parseInt(st.nextToken());

		int[] copy = arr.clone();
		int idx = 0;
		Arrays.sort(copy);
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		for (int i = 0; i < copy.length; i++) {
			if(!map.containsKey(copy[i])) map.put(copy[i], idx++);
		}
		
		for (int i = 0; i < arr.length; i++) bw.write(map.get(arr[i]) + " ");
		bw.flush();
	}
}