문제 출처

단계별로 풀어보기 > 정렬 > 좌표 압축
https://www.acmicpc.net/problem/18870

문제 설명

N개의 수가 주어질 때, 각각의 수마다 주어진 수 중 몇 번째 번호인지 출력하라.

접근 방법

배열 2개를 생성하여 하나는 원본, 하나는 오름차순 정렬을 진행한다.
오름차순 정렬한 배열을 바탕으로 HashMap을 만들어 각 원소마다 rank를 기록하고,
기록한 내용 바탕으로 원본 배열의 요소를 key로 HashMap에서 꺼내와 출력한다.

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

public class 좌표_압축 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int[] arr2 = new int[N];
        for(int i = 0; i<N; i++){
            int n = Integer.parseInt(st.nextToken());
            arr[i] = n;
            arr2[i] = n;
        }

        Arrays.sort(arr2);

        HashMap<Integer,Integer> hm = new HashMap<>();
        int rank = 0;

        for(int num : arr2){
            if(!hm.containsKey(num)){
                hm.put(num, rank++);
            }
        }

        StringBuilder sb = new StringBuilder();

        for(int num : arr){
            sb.append(hm.get(num)).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

Review

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

public class 좌표_압축_review {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());

        int arr[] = new int[N];
        int sorted[] = new int[N];

        for(int i = 0; i<N; i++){
            int el = Integer.parseInt(st.nextToken());
            arr[i] = el;
            sorted[i] = el;
        }

        Arrays.sort(sorted);

        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int rank = 0;

        for(int j = 0; j<N; j++){
            if(!hashMap.containsKey(sorted[j])) {
                hashMap.put(sorted[j], rank++);
            }
        }

        StringBuilder sb = new StringBuilder();

        for(int k : arr){
            sb.append(hashMap.get(k)).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();


    }

}

알게된 점

문제에서
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
부분에서 이해하기가 어려워서 다른 사람들 풀이를 보고 문제를 이해했다.
뭔가 이해하기 모호했던 것 같다.

문제푼 흔적

Review