[백준] 18870 - 좌표 압축 | Java

📌 문제 정보

[18870: 좌표 압축]

💡 접근 방식

단순히 나보다 작은 수가 몇 개 있는지 찾으면 되는 문제이다.

처음엔 원본 배열과 정렬된 배열을 따로 만들어서 mputIfAbsent로 중복 처리 해서 map에 저장하도록 풀었다. 그런데 단순히 정렬만 하면 같은 값이 배열에 남아 있어서 좌표 압축이 제대로 되지 않았다.

그래서 정렬된 배열을 따로 두지 않고 TreeSet을 사용해서 중복처리와 정렬을 함께 해주었다~

✅ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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());

        int[] arr = new int[n];
        TreeSet<Integer> set = new TreeSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());

            arr[i] = num;
            set.add(num);
        }

        Integer[] sorted = set.toArray(Integer[]::new);

        for (int i = 0; i < sorted.length; i++) {
            map.put(sorted[i], i);
        }

        StringBuilder sb = new StringBuilder();

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

        System.out.println(sb);

    }

}

🧠 배운 점 & 회고

TreeSet을 사용하는 것과 HashSet + sort를 하는 것을 비교해보았다. 아래 결과에서 첫 시도가 TreeSet이고 두번째가 HashSet 후 정렬이다.
TreeSet은 삽입마다 정렬을 해주어야 하기 때문에 더 느릴 거라 생각했는데 1초나 빨랐다..
HashSet을 리스트가 아니라 배열로 바꾸고 정렬해서 그런가?

🧾 결과