[CLASS 3: 정렬] 백준 18870 좌표 압축

18870번: 좌표 압축

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

 

# 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int[] origin = new int[n];	// 원본 배열
        int[] sorted = new int[n];	// 정렬할 배열
        HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();	// rank를 매길 HashMap

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            // 정렬할 배열과 원본 배열에 값을 저장
            sorted[i] = origin[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++;		// map에 넣고나면 다음 순위를 가리킬 수 있도록 1을 더해줌
            }
        }

        for(int key : origin) {
            int ranking = rankingMap.get(key);	// 원본 배열 원소(key)에 대한 value(순위)를 가져옴
            sb.append(ranking).append(" ");
        }
        System.out.println(sb);
        br.close();
    }
}

• 원본 배열과 정렬할 배열을 함께 생성하고 배열 정렬 이후 정렬 배열을 순회하며 HashMap에 원소와 순위를 넣어주면 되는 문제였다.

 

참고한 블로그는 아래이다. ( •̀ ω •́ )✧

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