2022.02.23 60일차

백준 18870번 (좌표 압축)

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

나의 풀이

1. TreeSet, int배열, Map 사용하기
2. TreeSet을 활용해서 중복없애면서 오름차순으로 x좌표 정렬
3. int배열로 x좌표 할당
4. Map을 활용하여 탐색하면서 키에 TreeSet값, 값에 count를 1씩 증가시키면서 추가
5. int배열을 탐색하면서 Map에 키로 활용하여 값 출력

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        Set<Integer> set = new TreeSet<>();
        int[] nArr = new int[N];
        Map<Integer, Integer> map = new HashMap<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(st.nextToken());
            set.add(x);
            nArr[i] = x;
        }

        int count = 0;
        for (Integer integer : set) {
            map.put(integer, count);
            count++;
        }

        for (int i : nArr) {
            bw.write(map.get(i) + " ");
        }
        bw.close();
    }
}

생각하기

• HashSet 정렬 -> List 활용

ArrayList<Integer> al = new ArrayList<>(set);
Collections.sort(al);