백준 18870번 : 좌표 압축(Java)

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

18870번: 좌표 압축

---

[풀이]

 

• 정렬을 이용한 문제였습니다.
• 기존 배열은 정렬 시킬 경우, 이후 기존 배열의 각 값의 위치를 알 수 없으므로 clone() 메소드를 통해 깊은 복사를 합니다.
• Map의 key는 좌표값을, value는 좌표값에 대한 최소 인덱스를 저장합니다.
• 만약, Map에 이미 있는 값이라면 무시하고, 없는 값이라면 좌표값과 인덱스를 저장하며 하나 증가시킵니다.
• 값을 가져올 땐느 기존 배열의 좌표값을 입력해 value를 가져오면 됩니다.

---

[코드]

 

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

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(), " ");
		int[] arr = new int[n];
		Map<Integer, Integer> map = new HashMap();
		StringBuffer sb = new StringBuffer();
		int idx = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int[] copyArr = arr.clone();
		Arrays.sort(copyArr);
		for (int i : copyArr) {
			if (!map.containsKey(i)) {
				map.put(i, idx++);
			}
		}

		for (int i : arr) {
			sb
				.append(map.get(i))
				.append(" ");
		}

		System.out.println(sb);
	}
}