[Silver II] 좌표 압축 - 18870

문제 링크

성능 요약

메모리: 366240 KB, 시간: 2024 ms

분류

값 / 좌표 압축, 정렬

제출 일자

2024년 10월 23일 15:24:55

문제 설명

수직선 위에 N개의 좌표 X₁, X₂, ..., X_N이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

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

X₁, X₂, ..., X_N에 좌표 압축을 적용한 결과 X'₁, X'₂, ..., X'_N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X₁, X₂, ..., X_N이 주어진다.

출력

첫째 줄에 X'₁, X'₂, ..., X'_N을 공백 한 칸으로 구분해서 출력한다.

예제 입력

5
2 4 -10 4 -9

예제 출력

2 3 0 3 1

좌표의 최솟값을 0으로 설정하고,

나머지 숫자들은 최솟값과의 차이를 계산해 1씩 증가시켜

좌표를 압축할 수 있다.

1. 주어진 배열을 오름차순으로 정렬한다.

2. Map에 기존 값과 압축된 좌표를 입력한다.

3. 기존 배열을 순회하며 압축된 좌표를 출력한다.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        int[] sortedList = list.stream().distinct().sorted().mapToInt(i -> i).toArray();
        Map<Integer, Integer> map = new HashMap<>();
        int num = 0;

        for (int i : sortedList) {
            map.put(i, num);
            num++;
        }

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

        System.out.println(sb);
        br.close();
    }
}