[백준] 18870번 : 좌표 압축

좌표 압축

---

문제 풀이

처음에 제목이 좌표 압축이라 무슨 문제지 싶었지만, 숫자 배열에서 우선 순위를 매기면 되는 문제였다.
정말 예전에 비슷한 문제를 풀어본 것 같았는데 이번 문제는 $-10^9 ≤ Xi ≤ 10^9$ 이라서 시간 초과가 났었다.

Map을 써야겠다는 생각이 들었지만, 마땅한 코드가 생각나지 않아서 블로그를 참조했다..
이분의 블로그를 참조하면 몰랐던 부분까지 알게되어서 자주 애용하게 되는 것 같다.
내가 이렇게 설명할 수 있는 수준까지 꾸준히 풀어봐야겠다!

여튼 문제를 풀이해보자면
1. 원래 순서를 저장하는 배열(origin)과 정렬된 배열(sorted)을 준비한다.
2. 정렬된 배열을 HashMap에 저장하는데, 중복된 숫자가 들어오면 무시해준다. (같은 순위를 가지기 때문에!)
3. origin 배열에서 하나씩 꺼내 HashMap의 key에 대응되는 value 값을 뽑아서 출력!

알고리즘 자체는 매우 간단하다.
이러한 유형의 문제는 자주 나오기 때문에 이번 문제에서 확실히 이해하고,
이런 알고리즘을 사용하는 변형 문제들을 풀기 위한 기초를 다져놓는 것이 중요한 것 같다.

블로그에서 나온 예시로는

• 2차원 그리드에서 특정 좌표에서 가장 멀리 갈 수 있는 최단 거리 좌표
• 데이터 자체를 압축 하는 방식
• 세그먼트 트리 부분

이러한 압축 관련 부분에서 자주 등장한다기에 위와 같은 개념을 응용하여 확장할 수 있게 정확히 이해하고가자!

추가로 이 문제는 print로 계속 찍었을 때, 시간초과가 나는 경우도 있어서
많은 양을 print해야 할때에는 StringBuilder를 사용하는 걸 추천한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int[] origin, sorted;
    static HashMap<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());

        origin = new int[n];
        sorted = new int[n];

        st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<n; i++) {
            origin[i] = sorted[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(sorted);

        solution();
		
        // HashMap에서 원본 배열에 원소값에 해당되는 key의 value 값 찾기
        StringBuilder sb = new StringBuilder();
        for(int key : origin) {
            int rank = map.get(key);
            sb.append(rank).append(" ");
        }
        System.out.println(sb);
    }


    private static void solution() {
        int rank = 0;
        for(int v : sorted) {
            if(!map.containsKey(v)) { // 중복 체크
                map.put(v, rank);
                rank++;
            }
        }
    }
}