Backjoon 18870.좌표 압축

숫자가 여러개 주어진다.

해당 숫자의 크기순서를 출력한다.

 

예를 들어

2 4 -10 4 -9

가 입력되면

제일 작은수대로 정렬하면 다음과 같다.

-10 -9 4 4 2

이렇게 나열된 숫자의 각 인덱스를 원래 순서대로 출력한다.

이 때 4는 중복되므로 인덱스가 증가하지 않는다. 

따라서 

-10 -9 4 4 2 는

0 1 2 2 3 의 인덱스를 가지며 이 배열을 원래 배열대로 출력하면

2 3 0 3 1 이 된다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

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

        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];

        String[] line = br.readLine().split(" ");
        for(int i = 0 ; i < n ; i++){
            nums[i] = Integer.parseInt(line[i]);
        }

        //배열을 복사하고 정렬
        int[] sorted = Arrays.copyOf(nums, n);
        Arrays.sort(sorted);

        //정렬한 대로 탐색
        //map을 사용하며 key값을 입력된 값
        //value 값을 rank 변수를 사용한다.
        //rank변수는 새로운 값이 나오면 ++ 된다.
        Map<Integer, Integer> map = new HashMap<>();
        int rank = 0;
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(sorted[i])) {
                map.put(sorted[i], rank++);
            }
        }

        //원래 배열의 i 번째 원소를 map에서 찾고
        //map에서 찾은 원소의 value를 출력한다.
        for (int i = 0; i < n; i++) {
            bw.write(map.get(nums[i]) + " ");
        }

        bw.flush();
        bw.close();
        
    }
}

 

이런 구성을 위해 Map 구조를 사용했다.

 

1.원래 배열의 복사본을 만든다.

2.복사본을 오름차순 정렬한다.

3. hashmap을 생성, 카운트 값 역할을 할 변수 rank를 생성한다.

4.오름차순 된 복사본을 key 값으로 사용하고 value 값을 rank 변수를 사용한다.

4-1.rank변수는 기본적으로 map의 다음요소로 넘어갈 때 +1이 되지만 같은 다음값이 이전값과 같을 경우 증가하지 않는다.

5.원래 배열을 순차적으로 탐색하며 hashmap에서 값을 검색하여 value값을 출력한다.

 

Java_Problem/Backjoon18870CoordinateCompression.java at main · KwonYunJe/Java_Problem