[백준] 18870번: 좌표 압축 자바

📎 문제 출처

---

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

📌 문제 설명

---

❓ 풀이 방법

---

처음에는 아래와 같이 이중 for문을 사용하여 현재 원소보다 더 작은 원소를 찾으면 hashmap의 값을 증가시키는 방법으로 풀었는데 정답은 나오지만 시간 초과로 통과하지 못했다.

		int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            if(map.containsKey(arr[i])) continue;
            map.put(arr[i], 0);
        }
        for(Integer i : map.keySet()) {
            for(Integer j : map.keySet()) {
                if(i > j) map.put(i, map.get(i) + 1);
            }
        }

이를 해결하려면 입력된 배열 arr를 정렬한 배열 sorted를 따로 저장하여 사용해야 한다.
정렬한 배열의 값을 hashmap이 key 값으로 가지고 있지 않을 경우 hashmapp에 추가하는데
이 때 value 값을 현재까지 map에 추가된 원소의 개수로 하면 현재 원소보다 작은 원소의 개수를 알 수 있게된다.

📌 Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n];
        int[] sorted = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sorted[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(sorted);

        HashMap<Integer, Integer> map = new HashMap<>();
        int cnt  = 0;
        for(int i = 0; i < n; i++) {
            if(map.containsKey(sorted[i])) continue;
            map.put(sorted[i], cnt++);
        }

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

        System.out.println(sb.toString());
    }

}