[백준] 18870 - 좌표 압축 - JAVA[자바]

 

[접근 방법]

"좌표 압축" 은 coordinate Compression(좌표 압축) 이라고 하는 문제의 한 카테고리를 차지하고 있다. 

데이터의 범주가 너무 크거나, 단순화하여 문제를 세분화 시킬 때 사용할 수 있다.

 

이번 문제를 해석하면

배열의 각 원소에 대해 순위를 매긴다

라고 생각하면 된다. 

 

예제 입력 1에서

{2, 4, -10, 4, -9} 가 있을 때 내림차순으로 순위를 매긴다면 {2, 3, 0, 3, 1} 이 된다. 

 

즉,

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

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

이때 정렬을 떠올리는 것이 좋은 접근방법이다.

또, "2. 중복되는 원소는 같은 순위를 갖는다."  에서 중복되는 원소를 하나만 갖는게 중요하므로 자료구조 중 Set 혹은 Map을 사용하는 것이 좋은 접근 방법이다. 

 

중복되지 않으면서
각 원소에 대한 순위를 매길수 있는 자료형은?
=> HashMap 자료구조가 적합하다. 

 

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;

import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.Arrays;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());       
        
        int[] origin = new int[N]; //원본 배열
        int[] sorted = new int[N]; //정렬할 배열
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();
        
        for(int i = 0; i<N; i++){
            origin[i] = sorted[i] = Integer.parseInt(st.nextToken());
        }
        
        //정렬할 배열에 대해 정렬을 수행
        Arrays.sort(sorted);
            
        //정렬된 배열 순회하면서 map에 넣기
        int rank = 0;
        for (int v: sorted){
            if(!rankingMap.containsKey(v)){
                rankingMap.put(v, rank);
                rank++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int key: origin){
            int ranking = rankingMap.get(key); // 원본 배열 원소(key)에 대한 순위(value)를 갖고온다.
            sb.append(ranking).append(' ');
        }
        
        System.out.println(sb);
    }
}

 

해당 로직에서 사용한 풀이 중 중요한 부분은

1. HashMap을 만들어주기 위해서 정렬할 배열을 사용한다.

2. 원본 배열을 유지하여 HashMap에서 값을 꺼내오는 동시에 순위가 매겨진다.

3. map에 원소를 넣을 때 무작정 넣으면 안되고, map에 똑같은 값이 들어있지 않을 경우에만 원소와 rank 값을 넣어주어야 한다.

는 점이다.

3번을 지키지 않으면 중복되는 원소가 들어왔을 때 rank값이 올라 중간에 '3'이 없어지고, '4'로 값이 건너뛰어지게 된다.