[BackJoon]18870번

문제

 

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

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

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

 

입력

 

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2,..., XN이 주어진다.

 

출력

 

첫째 줄에 X'1, X'2,..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

풀이

 

문제만 읽어선 무슨 소린지 잘 와닿지 않으니까 예제의 입출력을 하나 살펴보자.

 

그러니까 주어진 숫자를 0부터 (중복을 제거한) 수의 개수 - 1까지 압축하라는 뜻이다.

 

위의 예를 이용하면 중복을 제거한 수는 아래의 네 개가 되고,

 

가장 작은 숫자를 0, 가장 큰 숫자를 4 - 1 = 3으로 삼아

 

맨 처음 주어진 좌표를 해당 숫자로 바꿔 "압축"하라는 뜻이다.

 

문제가 무슨 뜻인지 이해되고 나면 코드로 옮기는 일은 그다지 어려운 일이 아니다.

 

제한조건으로 주어질 수의 범위가 거의 정수형의 절반에 달하기 때문에 카운팅 정렬을 쓰기보단

 

그냥 내장 정렬을 쓰기로 마음을 먹었다.

 

이어서 정렬의 대상이 될 값을 받을 list와 좌표 압축에 사용할 map을 생성한 뒤,

 

좌표를 받아 중복을 제거한 뒤 정렬, 작은 순서대로 map의 키값으로 넣어주며 밸류를 +1 시켰다.

 

이후엔 list를 순회하며 해당 값을 키로 삼아 밸류 값을 BuffueredWritter에 넣어주었고, 출력으로 끝.

 

이상을 먼저 그림으로 보면 아래와 같다.

 

계속해서 코드를 보자. 너무 짧아서 허무하다.

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Prob18870_2 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        List<Integer> sortedList = list.stream()
                .distinct()
                .sorted()
                .collect(Collectors.toList());

        int num = 0;

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

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

        bw.flush();
        bw.close();
    }
}