[Java] 백준(실버-2) 18870번 - 좌표 압축

문제 풀이

---

좌표 압축이라고 해서 문제 내용을 이해하는데 시간이 좀 걸렸지만, 테스트케이스를 보고서 유추를 할 수 있었다.
바로 원소들의 순위를 매겨 정해진 순위를 출력하는 것이다.

예시를 들어서 보면 이해하기 아주 쉽다.

arr = [2,4,-10,4,-9]
-10: 0순위
-9: 1순위
2: 2순위
4: 3순위
4: 3순위

위 예시를 통해 아래와 같은 조건을 생각해볼 수 있다.

• 제일 작은 값이 높은 순위를 가진다.(0순위 부터)
• 같은 값은 같은 순위를 가진다.

아이디어 도출

알고리즘 구현을 위해 생각한 아이디어는 다음과 같다.

• 원본 배열을 토대로 오름차순 정렬된 배열을 만든다.
• 정렬된 배열에서 원소 중복을 제거하여 원소와 순위를 Map에 저장한다.
• 원본 배열을 순회하며 Map의 value 값을 조회하여 출력한다.

아이디어는 단순하게 생각해보면 단순하다.
그렇다면 코드를 작성해보자.

int N = Integer.parseInt(br.readLine());

String[] arr = new String[N];
arr = br.readLine().split(" ");

int[] sorted_arr = Arrays.stream(arr).mapToInt(Integer::parseInt).toArray();

N을 입력받고 원본배열인 arr배열에 입력값을 받아 저장한다.
그리고 stream의 mapToInt를 활용해 int형 배열로 변환한다.

Arrays.sort(sorted_arr);

LinkedHashSet<Integer> set = new LinkedHashSet<>();
HashMap<Integer, Integer> hm = new HashMap<>();

for(int n : sorted_arr) set.add(n);

int idx = 0;
for(int n : set) {
    hm.put(n, idx++);   
}

그리고 int형 배열을 오름차순 정렬한 뒤, 중복이 허용되지 않으며, 입력 순서가 보장되는 LinkedHashSet에 정렬한 sorted_arr 배열의 원소를 담는다.
그리고 set을 순회하며 hashMap에 원소와 인덱스를 저장한다. (낮은 값부터 큰 값으로 순회하기에 인덱스가 순위가 된다.)

StringBuilder sb = new StringBuilder();
for(int i=0; i<arr.length; i++) {
    sb.append(hm.get(Integer.parseInt(arr[i])) + " ");
}

bw.write(sb.toString()+"\n");

그리고 원본배열 arr를 순회하며 hashMap에서 순위값을 get() 메서드로 가져와 출력하면 된다.
문제에서는 한줄에 공백값 기준으로 출력하기에 StringBuilder에 담아 출력하였다.

작성코드

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

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

        int N = Integer.parseInt(br.readLine());

        String[] arr = br.readLine().split(" ");
        int[] sorted_arr = Arrays.stream(arr).mapToInt(Integer::parseInt).toArray();

        Arrays.sort(sorted_arr);

        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        HashMap<Integer, Integer> hm = new HashMap<>();
        
        for(int n : sorted_arr) set.add(n);
        
        int idx = 0;
        for(int n : set) {
            hm.put(n, idx++);   
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<arr.length; i++) {
            sb.append(hm.get(Integer.parseInt(arr[i])) + " ");
        }

        bw.write(sb.toString()+"\n");

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

회고

• 같은 값의 경우 같은 순위를 부여해야 하기 때문에 중복이 허용되지 않고 입력 순서가 보장되는 LinkedHashSet을 활용할 수 있었다.
• 이 문제는 차후 압축 관련 알고리즘 문제를 풀 때 생각날 수 있을 것 같다.