백준 18870번: 좌표 압축

문제 이해가 좀 어려운데 알고보면 쉽다.

첫 번째 예제 입력의 배열 [2, 4, -10, 4, -9]에서

• 1번째 원소) 2보다 작은 수는 [-10, -9] 2개이다
• 2번째 원소) 4보다 작은 수는 [2, -10, -9] 3개이다
• 3번째 원소) -10보다 작은 수는 0개이다
• 4번째 원소) 4보다 작은 수는 [2, -10, -9] 3개이다
• 5번째 원소) -9보다 작은 수는 [-10] 1개이다

그러므로 출력은 [2, 3, 0, 3, 1]이다.
즉 자신보다 작은 수의 개수를 찾아서 출력하면 된다.

가장 먼저 든 생각은 이중 반복문 돌면서 자신보다 작은 수를 모두 탐색하는 것이지만 우리의 백준 문제가 그렇게 간단할 리가 없다.

---

정렬을 이용하면 간단하다.

첫 번째 입력인 [2, 4, -10, 4, -9]를 정렬하면 [ -10, -9, 2, 4, 4]이다.
첫 번째 원소(-10)는 가장 작은 원소이므로 이보다 작은 수의 개수는 반드시 0이다.

두 번째 원소의 값은 반드시 첫 번째 원소보다 크거나 같다.
크면 출력++, 같으면 출력 값을 그대로 둔다.
여기에서는 두 번째 원소(-9)가 첫 번째 원소(-10)보다 크므로 0++ 즉, 1을 출력한다.

세 번째 원소의 값도 반드시 두 번째 원소보다 크거나 같다.
여기에서는 세 번째 원소(2)가 첫 번째 원소(-9)보다 크므로 1++ 즉, 2을 출력한다.

즉, x[i-1] < x[i] 이면 cnt ++, 아니면 cnt값은 그대로인 것이다.

계속해서 같은 방식으로 진행하면
네 번째 원소(4)는 세 번째 원소(3)보다 크므로 출력은 2++ 즉, 3이 된다.

다선 번째 원소(4)는 네 번째 원소(4)와 같으므로 출력은 그대로 즉, 3이다.

그리고 이 결과를 원래 입력배열과 매칭하여 출력하면 된다.

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.StringTokenizer;

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 inputArray[] = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			inputArray[i] = Integer.parseInt(st.nextToken());
		}

		// 정렬을 위해 복사
		int sortedArray[] = Arrays.copyOf(inputArray, n);
		// 입력된 정렬
		Arrays.sort(sortedArray);

		int cnt = 0;
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); // 입력 배열과 결과 값 맵핑하기 위해 HashMap 이용
		map.put(sortedArray[0], 0);
		for (int i = 1; i < n; i++) {
			// i번째 원소가 i-1번째 원소보다 크면 cnt++
			if (sortedArray[i] > sortedArray[i - 1]) {
				cnt++;
			}
			map.put(sortedArray[i], cnt);
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			int xi = map.get(inputArray[i]);
			sb.append(xi + " ");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}