[백준] S2 18870번 좌표 압축 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

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. 좌표 압축은 가장 값이 작은 것을 기준으로 0부터 값이 올라간다.

2. 입력받은 것을 정렬을 해줘야 하는데 정렬을 해주면 마지막 출력할 때 비교 값이 없으므로 copy를 만들어준다.

3. HashMap에 입력 받은 값이 정렬된 것을 다른 값일 경우 0부터 값을 올려가면서 넣어준다.

4. HashMap에 있는 값에 copy의 값이 Key로 해당하는 ㅍalue 값으로 출력한다.

[접근]

1. 배열을 오름차순으로 정렬해서 HashMap에 해당 값을 키값으로 하는 value를 0부터 증가시켜가면서 넣어준다.

2. copy된 값을 HashMap에 Key값으로 Value를 출력한다.

3. 그냥 출력하려고 했는데 시간 초과가 발생했다. 이를 해결하기 위해 StringBuilder를 사용해서 출력해 주었다.

[코드]

package BOJ_silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main_S2_18870 {
	static int n;
	static int[] arr;
	static int[] copy;
	static HashMap<Integer, Integer> map;
	static int cnt = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		n = Integer.parseInt(br.readLine());
		
		arr = new int[n];
		copy = new int[n]; // arr을 정렬해야하기 때문에 최종 출력할 때를 위해 복사 
		
		map = new HashMap<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// copy와 arr에 값 입력
		for (int i = 0; i < n; i++) {
			copy[i] = arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 배열 정렬
		Arrays.sort(arr);
		
		// 해쉬맵에 arr[i] 값을 순서대로 넣는다.
		for (int i = 0; i < n; i++) {
			if (!map.containsKey(arr[i])) // 이미 값이 들어있는 거라면
				map.put(arr[i], cnt++); // 그 다음 값으로 넣는다
		}
		
		// 입력된 값에 해당하는 cnt 값을 출력한다.
		for (int i = 0; i < n; i++) {
			sb.append(map.get(copy[i])).append(" ");
		}
		
		System.out.println(sb);
	}
}