📌 문제

[18870] 좌표 압축

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

✔️ 제한

1 ≤ N ≤ 1,000,000
-10^9 ≤ Xi ≤ 10^9

💡 코드

❓ Arrays.sort()로 정렬해서 해당 요소보다 작은 수, 즉 정렬 후 앞에 위치한 요소의 수를 카운트해서 출력할 생각이였는데 막상 그렇게 코드를 짜니까 정렬된 순서대로 출력돼서 정답이랑 순서가 다르게 나왔다,,!

이를 해결하기 위해 HashMap을 사용해서 키에 인덱스를 담고, 값에 요소를 담아 값 기준으로 정렬한 후에 인덱스 순서로 출력해보면 어떨까? 라고 생각해서 짜봤는데 Map 자체는 정렬이 안되고 키나 깂을 따로 List에 저장해서 정렬해야 하는데 이렇게 되면 위랑 다를 게 없어서 또 막힘,,

⏱️ 하도 막혀서 걍 순정 for문으로 풀어봤는데 역시나 시간 초과 ^^~

import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws 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<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<n;i++) {
			int cnt = 0;
			for(int j=0;j<n;j++) {
				if(arr[i]> arr[j]) cnt++;
			}
			sb.append(cnt + " ");
		}
		bw.write(sb + "\n");
		
		br.close();
		bw.close();
	}
}

✅ 도저히 모르겠어서 결국 구글링의 힘을 빌렸고, HashMap을 쓴다는 접근 자체는 맞았다,,! 근데 나처럼 처음부터 냅다 쓰는 건 아니였음 ㅎ

일단 arr[]에 요소들을 담아주고, 해당 요소들의 순서를 남겨놓기 위해 정렬용 배열 sort[]를 선언하여 Arrays.sort(sort)를 수행한다. 정렬 수행 후 map을 사용하여 <좌표, 최소 인덱스>를 저장한다. 이후 arr[]와 map.get()을 통해 특정 요소와 같은 값을 가지는 좌표에 해당하는 값을 출력해주면 끝!

import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws 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<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] sort = arr.clone();
		Arrays.sort(sort);
		
		Map<Integer, Integer> map = new HashMap<>();
		int idx = 0;
		for(int num : sort) {
			if(!map.containsKey(num)) map.put(num, idx++);
		}
		
		StringBuilder sb = new StringBuilder();
		for(int num : arr)
			sb.append(map.get(num)).append(" ");
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}