[백준 알고리즘 JAVA] 18870번 좌표 압축

https://www.acmicpc.net/problem/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
• -109 ≤ Xi ≤ 109

 

package week1;

import java.util.*;

public class Q18870 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        // 1. 좌표를 담을 List를 생성. 좌표를 입력받아 list에 추가
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            list.add(scanner.nextInt());
        }

        //2. 작은수부터 정렬
        List<Integer> sorted = list.stream()
                .sorted()
                .toList();

        // 3. map을 이용해서 정렬된 리스트의 값을 꺼내서 하나씩 순위를 매김.
        // 단, 중복된 값이 들어있을 경우 수행하지 않음.
        Map<Integer, Integer> ranking = new HashMap<>();
        int rank = 0;

        for (int i = 0; i < sorted.size(); i++) {
            int num = sorted.get(i);
            if(!ranking.containsKey(num)){
                ranking.put(num, rank);
                rank++;
            }
        }

        //4. 좌표 압축을 적용한 결과를 담을 List compression생성
        List<Integer> compression =  new ArrayList<>();

        //5. compression에 맵에 있는 value를 하나씩 꺼내서 넣음
        for (Integer i : list) {
            compression.add(ranking.get(i)); // get() 매개변수 key, 반환타입 value
        }

        //6. System.out.println(compression);으로 출력하니 시간초과 떠서 StringBuilder를 사용해서 출력
        StringBuilder sb = new StringBuilder();

        for (Integer i : compression) {
            sb.append(i).append(" ");
        }

        System.out.println(sb);

//        for (Integer i : compression) {
//            System.out.print(i + " ");
//        }
    }
}