[백준] S2 18870번 좌표 압축 (Java)

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

👉 문제

이번 문제는 origin 배열을 sorted 배열에 따로 정렬한 뒤, 정렬된 값을 중복되지 않는 선에서 HashMap에 원소와 그에 대응되는 순위를 넣어준다. 그리고 origin의 각 값을 key로서 HashMap에서 value를 뽑아 출력하는 방식으로 풀 수 있다.

👉 풀이

1. 처음에는 위에서 말한 풀이를 생각하지 못했다. ArrayList에 값을 넣은 후 최소값(min)에 따라 num(rank)를 증가시켜서 새 배열(newArr)에 넣어주는 식으로 풀었다. 근데 아니나 다를까 시간초과 ^^;

package Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class _18870_1 {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        ArrayList<Integer> arr = new ArrayList<>();
        int[] newArr = new int[N];
        int num = 0;

        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < N; i++) {
            int min = Collections.min(arr);
            int idx = arr.indexOf(min);

            arr.set(arr.indexOf(min), (int) Math.pow(10, 9)); // 인덱싱 변화없도록 최대값으로 만듬
            newArr[idx] = num;

            if (min != Collections.min(arr)) {
                num++;
            }
        }

        for(int i=0; i<N;i++){
            sb.append(newArr[i]).append(" ");
        }

        System.out.println(sb);
    }
}

2. 시간초과를 하지 않도록 HashMap을 써야할 것 같다는 생각은 했지만 정확히 어떻게 구성해야할지 고민하다가 구글링으로 찾은 블로그에서 해답을 얻었다.(참고는 아래에)

원본 배열(origin)과 정렬 할 배열(sorted), 정렬한 값에 대한 key, rank를 두기 위한 HashMap을 이용한다. 정렬된 배열을 순회하면서 앞선 원소가 순서가 매겨졌고, 중복되지 않을 때만 map에 원소와 그에 대응하는 순위를 넣어준다. 그러고 후에 origin의 값이 key로서 value(rank)를 출력하니 시간초과를 해결할 수 있었다.

package Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class _18870_2 {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] origin = new int[N]; // 원본 배열
        int[] sorted = new int[N]; // 정렬 할 배열
        HashMap<Integer, Integer> map = new 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 s : sorted) {
            /**
             * 앞선 원소가 이미 순위가 매겨졌다면, 중복되지 않을 때만
             * map에 원소와 그에 대응되는 순위를 넣어준다.
             */
            if (!map.containsKey(s)) {
                map.put(s, rank);
                rank++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int key : origin) {
            int ranking = map.get(key);
            sb.append(ranking).append(' ');
        }

        System.out.println(sb);
    }
}

### 👉 성능

채점번호 : 69609888 - 방법 2 : HashMap 이용
채점번호 : 69600981 - 방법 1 : ArrayList 이용

속도 차이가 단순히 HashMap을 사용해서 줄어든 것은 아니겠지만 확실히 정의된 자료구조를 이용하는게 성능도 좋고 빠른 것 같다..

👉 참고

https://st-lab.tistory.com/279