[자바] 18870 - 좌표 압축 Java(자바) // Study 메모용

좌표 압축이라고 문제가 되어 있다. 정확히 표현하자면 좌표 압축 알고리즘을 활용한 ranking list를 만드는 문제라고 봐야함.

 

위와 같은 문제 부류를 coordinate Compression(좌표 압축)이라고 하는데, 어떤 특정한 알고리즘이 존재하는게 아니라, 하나의 카테고리라고 보면 됨. 1차원 데이터의 경우는 위 문제처럼 순위를 매기거나 하는 문제들을 쓸때 사용함. 

대부분 2차원 이상의 좌표에서 데이터 압축할 때 접하게 되는 경우가 많음.

 

특히 데이터의 범위가 매우 크거나, 단순화 해야 할 일들이 있을 때 많이 쓰이게 된다.

대표적인 예시로 GPS 좌표 압축같이 2차원 혹은 3차원 데이터를 그리드로 놓고 보았을 때 데이터 값들을 단순화하여 압축하거나(손실 압축) 특정 공식에 의해 무손실 압축을 하는 등 데이터의 양을 압축시키는 방식 등이 있다. 

 

 

ex) 

2차원 그리드에서 특정 좌표에서 가장 멀리 갈 수 있는 최단 거리 좌표를 구하고자 할때, 장애물은 빨간색 블럭으로 해당 블럭을 넘어다닐 수 없다. 

 

보통 해당 문제는 BFS 알고리즘을 사용하여 풀이 , But  좌표가 많다면 이런 문제를 풀때 좌표를 압축하여 푼다. 

 

보면 각 블럭(좌표)을 새로운 그리드로 각 선분의 정점만 좌표로 두고 나머지 불필요한 좌표는 모두 지웠다. 

오른쪽 그림처럼 압축을 한 뒤, BFS로 탐색을 하고, 탐색 된 블럭에서 원본에서 압축 된 블럭 간격을 측정하여 거리를 계산 할 수 있음.. 

 

그러면 탐색해야 할 좌표가 매우 적어짐을 확인할 수 있음. 

 

위와 같이 불필요한 좌표를 날려 단순화 하는 방식도 있고, 데이터 자체를 압축 하는 방식도 존재한다. 

이러한 부류는 ZIP파일 같은 곳에서 많이 사용됨. 

 

해당 문제를 아주 쉽게 해석하면, 배열 각 원소값에 대한 '순위'를 매기는 것이다. 

예시) 

arr = {2,4,-10,4,-9}

여기서 각 원소를 순위로 매기자는 것이다. (낮은 값이 순위가 높다는 점을 유의) 

가장 낮은 값이 -10이 0 순위가 됨. 그 다음은 -9가 1순위 ... 이런식으로 진행된다. 

 

즉, rank로 보면 다음과 같음. 

rank = {2, 3, 0 , 3, 1}  이런식으로 진행됨 

 

이렇게 되기 위해서는 문제를 어떻게 접근하는 것이 좋은가? 

위 문제를 살펴보면 다음과 같이 두 가지 조건이 있다. 

 

1. 낮은 값이 높은 순위를 갖는다. (가장 높은 순위는 0순위다.) 

2. 중복되는 원소는 같은 순위를 갖는다. 

 

자, 하나의 조건씩 구체적으로 살펴보자. 

 

낮은 값이 높은 순위를 갖는 다는 것, 결국 순위를 정한다는 것은 오름차순으로 '정렬'을 했을 때 첫 번째 인덱스에 있는 원소가 가장 높은 순위를 갖고, 반대로 가장 마지막에 있는 원소가 가장 낮은 순위를 갖는다는 것을 의미한다. 

 

다음으로 중복되는 원소가 같은 순위를 갖는다는 것은 앞선 예제에서도 보았듯이 4라는 값에 대응되는 순위는 모두 3으로 같은 순위로 매칭이 되어야 한다는 것이다. 

 

이 부분은 무엇을 활용할 수 있는가? 중복되는 원소를 하나만 갖고 있을 수 있도록 하는 자료구조인 Set혹은 Map자료구조를 활용하면 되지 않을까? 

 

여기서 우리는 순위를 매겨야하므로, 중복되지 않으면서 각 원소에 대한 순위를 매길 수 있는 자료구조인 HashMap자료구조를 활용해보도록 하자. 

 

알고리즘 과정은 매우 단순하다. 

 

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Baekjoon18870 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int []arr = new int[N];
        int []copyArr = new int[N];
        for(int i=0;i<N;i++){
            arr[i]= copyArr[i]  = scan.nextInt();
            
        }
        
        Arrays.sort(copyArr);
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int i=0;
        for(int x: copyArr){
            if(!hashMap.containsKey(x)){
                hashMap.put(x,i);
                i++;
            }
        }        
        // key값이 같은 경우 value값을 가져온다.
        StringBuilder sb = new StringBuilder(); 
        for(int key : arr){
           int ranking = hashMap.get(key);
           sb.append(ranking+" ");
        }
        System.out.println(sb);
    }
}

 

참고 자료)

[백준] 18870번 : 좌표 압축 - JAVA [자바] (tistory.com)