[종만북] SORTGAME - Sorting Game (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-SORTGAME

 

 

풀이

  우선 생각해야 할 부분은, '한 수열에 같은 수가 두 번 출현하지 않는다고 가정해도 좋다. 모든 수는 1부터 1백만 사이의 정수' 라는 지문 부분이다. 1부터 1백만 사이로 입력이 들어오는게 의미가 있을까? 어차피 대소 관계 순서만 동일하다면 전혀 상관 없다. 따라서 값 압축을 통해 1부터 N까지의 값으로 우선 압축해서 생각하자.

 

  예를들어 N개가 '1000000 4 2 5000' 이렇게 들어왔다면, 압축해서 '4 2 1 3'와 같이 생각하면 된다.

또한 N은 최대 8 이므로, 정수 하나로 표현할 수 있다. 즉 위의 '4 2 1 3'은 '4213'에 해당한다.

private int compressedNum(int n, int[] arr) {
    int[] tmp = Arrays.copyOf(arr, arr.length);
    Arrays.sort(tmp);

    Map<Integer, Integer> compress = new HashMap<>();
    int to = 1;
    for (int cur : tmp)
        compress.put(cur, to++);

    int base = 0;
    for (int i = 0; i < n; i++) {
        base *= 10;
        base += compress.get(arr[i]);
    }

    return base;
}

 

  여기까지 보자면, 이제 1부터 1백만 사이의 수는 의미 없어졌고, N은 최대 8이다. N이 8일 경우, 우린 입력으로 주어진 수열을 '12345678'로 바꾸는데 필요한 최소 연산을 구해야 한다. 그리고 이 문제에서는 테스트 케이스의 수가 1000개로 매우 많으므로, 매번 실제로 '12345678'을 만들 때 까지 연산하는건 손해이다. 따라서 역으로 '12345678'에서 시작해 모든 수를 만들어봐서 횟수를 역으로 지정해두는 전처리를 하고, 각 테스트 케이스마다 O(1)로 바로바로 출력해주는게 더 효율적이다. 물론 N이 1부터 7인 구간도 마찬가지로 전처리를 해두면 된다.

 

  전처리는 N이 1부터 8인 구간에 대해 각각 '12345...' 라는 숫자부터 시작해 실제로 뒤집을 수 있는 모든 경우의 수를 bfs로 순차적으로 진행하면 된다. 어차피 정수로 떨어지므로 중복체크는 HashMap으로 처리하면 된다. (배열로 하게되면 각 자리수가 동일한게 있는 경우도 메모리에 있어야 하므로 손해다.). 이하 코드에서 s와 e가 어느 자리부터 어느 자리까지 뒤집을 것인지 정하는 부분이다. 예를들어 현재 숫자가 '12345678' 이고 s=1, e=3일 경우 rangeReverse()의 결과는 '14325678' 이다.

private void preComputation(final int len, Map<Integer, Integer> result, final int base) {
    Queue<int[]> q = new ArrayDeque<>();
    q.add(new int[]{base, 0});
    result.put(base, 0);

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int num = cur[0];
        int dist = cur[1];

        for (int s = 0; s < len-1; s++) {
            for (int e = s+1; e < len; e++) {
                int next = rangeReverse(num, len, s, e);

                if (result.containsKey(next)) continue;
                result.put(next, dist+1);
                q.add(new int[]{next, dist+1});
            }
        }
    }
}

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    private Map<Integer, Integer>[] answer = new Map[9];

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        init();
        int c = Integer.parseInt(br.readLine());
        while (c-->0) {
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n];

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

            sb.append(answer[n].get(compressedNum(n, arr))).append('\n');
        }
        System.out.print(sb);
    }

    private int compressedNum(int n, int[] arr) {
        int[] tmp = Arrays.copyOf(arr, arr.length);
        Arrays.sort(tmp);

        Map<Integer, Integer> compress = new HashMap<>();
        int to = 1;
        for (int cur : tmp)
            compress.put(cur, to++);

        int base = 0;
        for (int i = 0; i < n; i++) {
            base *= 10;
            base += compress.get(arr[i]);
        }

        return base;
    }

    private void init() {
        for (int i = 1; i <= 8; i++)
            answer[i] = new HashMap<>();

        for (int i = 1; i <= 8; i++) {
            int base = 0;
            for (int j = 1; j <= i; j++) {
                base *= 10;
                base += j;
            }

            preComputation(i, answer[i], base);
        }
    }

    private void preComputation(final int len, Map<Integer, Integer> result, final int base) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{base, 0});
        result.put(base, 0);

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int num = cur[0];
            int dist = cur[1];

            for (int s = 0; s < len-1; s++) {
                for (int e = s+1; e < len; e++) {
                    int next = rangeReverse(num, len, s, e);

                    if (result.containsKey(next)) continue;
                    result.put(next, dist+1);
                    q.add(new int[]{next, dist+1});
                }
            }
        }
    }

    private int rangeReverse(int num, final int len, final int s, final int e) {
        int pre = 1;
        for (int i = 0; i < len-s; i++) pre*=10;

        int post = 1;
        for (int i = 0; i < len-e-1; i++) post*=10;

        return (num/pre*pre + reverse(num%pre/post)*post) + num%post;
    }

    private int reverse(int num) {
        int result = 0;

        while (num != 0) {
            result *= 10;
            result += num % 10;
            num /= 10;
        }

        return result;
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.