[백준] 18870 좌표 압축 (JAVA)

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

18870번: 좌표 압축

풀이

 해당 문제는 가만히 보면 그냥 정렬하였을경우 해당 인덱스의 수보다 작은 수가 몇개가 있냐는 말과 같다. 그렇기 나는 기존 입력값이 들어가있는 origin배열과 정렬되어있는 sort배열 마지막으로 map을 만들어주었다. 우선 처음으로는 입력값을 origin배열과 sort배열에 입력을 받고 Arrays.sort메소드를 이용해 sort를 정렬해준다. 이후 이터레이터를 이용해 만약 map에 배열에 있는 값이 존재하지 않는다면 map에 넣어주고 수를 증가시켜준다. 코드가 그리 길지 않으니 코드를 보면 쉽게 이해가 될것이다.

 

코드

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

class Main{

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

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

        int [] sort = new int[N];
        int [] origin = new int[N];
        int [] zip = new int[N];

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

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

        Arrays.sort(sort);

        int rank = 0;
        for (int i : sort) {
            if(!map.containsKey(i)){
                map.put(i, rank++);
            }
        }

        for (int i = 0; i < N; i++) {
            bw.write(map.get(origin[i]) + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}