문제 번호 18870번 : 좌표 압축 - JAVA [자바]

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

문제 설명

 

좌표 압축 문제입니다. 문제만 봐서는 사실 정확하게 어떤 값을 출력하는 건지 알기가 쉽지 않습니다.

간단히 설명하면 각 원소의 순위를 매기는 것이라고 생각하면 됩니다.

첫 번째 예제를 보면 -10이 제일 작은 값임으로 0을 가지고

-9가 두 번째로 작은 값임으로 1을 가집니다.

4는 2개가 동시에 3을 가지게 됩니다.

이렇게 순위를 매기는 것이라는 것을 이해하게 되면 실제 문제 풀이는 어렵지 않습니다.

 

문제 풀이

 

어떻게 각 배열의 순위를 매기고 그 순위를 배열의 순서대로 출력할 수 있을까요? 

배열의 정렬을 먼저 해야 될 거 같습니다. 그래야 순위를 매기는 것이 수월한 테니깐요

HashMap을 사용해서 key의 정렬된 배열을 넣고 value에 순위를 넣으면 어떨까요?

그러면 원본 배열을 key로 HashMap에서 value을 찾아 출력해주기만 하면 되니깐요.

 

그림으로 설명해 보겠습니다.

 

이해가 되시나요? 중요한 점은 정렬 후 map으로 순위를 저장한다는 것입니다.

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

public class NUmber_18870 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] array = new int[n];//원본 배열
        int[] arraySort = new int[n];//정렬된 배열
        HashMap<Integer, Integer> rankMap = new HashMap<Integer, Integer>();//압축할 map

        //배열 입력
        for(int i=0; i<n; i++){
            array[i] = arraySort[i] = sc.nextInt();
        }

        //배열 정렬
        Arrays.sort(arraySort);


        //배열의 압축값을 map에 저장
        int rank = 0;

        for(int value : arraySort){
            if(!rankMap.containsKey(value)){
                rankMap.put(value,rank);
                rank++;
            }
        }

        //원본 배열의 순서대로 해당 압축 배열을 출력
        StringBuilder sb = new StringBuilder();
        for(int value : array){
            sb.append(rankMap.get(value)).append(' ');
        }

        System.out.println(sb);
    }
}

 

StringBuilder로 하지 않으면 시간 초가 오류가 나니 참고하시면 됩니다.