최소 회수로 정렬하기(뒤집어 정렬하기), 정렬하는 회수 찾기 - 너비 우선 탐색 알고리즘 문제(Java 1.8)

출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 

문제 (Sorting Game)

정수의 배열이 주어질 때 연속된 부분 구간의 순서를 뒤집는 것을 뒤집기 연산이라고 부릅시다.
예를 들어 배열 {3, 4, 1, 2}에서 부분 구간 {4, 1, 2}를 뒤집으면 {3, 2, 1, 4}가 됩니다.
중복이 없는 정수 배열을 뒤집기 연산을 이용해서 정렬하려고 합니다. 
필요한 최소한의 연산 수를 계산하는 프로그램을 작성하세요.
예를 들어 {3, 4, 1, 2}는 {3, 4}와 {1, 2}를 각각 뒤집고 전체를 뒤집으면 세번의 연산으로도 정렬할 수 있지만,
{4, 1, 2}를 먼저 뒤집고 {3, 2, 1}을 뒤집으면 두 번의 연산만으로 정렬할 수 있습니다.

 

시간 및 메모리 제한

프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C<=1000)가 주어지고, 각 테스트 케이스의 첫 줄에는 배열의 길이 n(1<=n<=8)이 주어집니다.
다음 줄에 n개의 정수로 배열의 원소들이 순서대로 주어집니다. 
한 배열에 같은 수가 두 번 출현하지 않는다고 가정해도 좋습니다.
모든 수는 1 이상 1백만 이하의 정수입니다.

 

출력

각 테스트 케이스마다 입력을 정렬하기 위해 필요한 최소 뒤집기 연산의 수를 출력합니다.

 

 

예제 입력

3
8
1 2 3 4 8 7 6 5
4
3 9999 1 2
3 
1000 2000 3000

 

예제 출력

1
2
0

 

풀이 설명

배열을 임의로 t 부분(t는 배열의 크기보다 작은 수)만큼 뒤집 었을 때
만들어 지는 배열을 정점으로 바라본다면
문제를 그래프로 변환해서 풀 수 있습니다.
정렬 된 배열을 만들기 위해 최소한으로 뒤집는 회수를 구하는 것이기 때문에
그래프의 너비우선 탐색을 이용해서 최단 거리를 찾는 문제로 변환할 수 있습니다. 

 

풀이 1

public class one {
    /**
     * 배열 자체를 정점으로 보고,
     * 뒤집기 연산으로 만들 수 있는 배열을 다른 정점으로 바라볼 때,
     * 최종으로 정렬된 정점까지의 거리를 구하면 되는 문제
     *
     * 이 때 핵심은 배열을 키 값으로 사용한다는 점이다.
     *
     * 배열을 그대로 사용할 경우, 주소 복사가 일어나서 배열의 값이 같아도 다른 객체로 인식할 수 있기 때문에 주의한다.
     * 이때, Arrays 클래스에서 제공하는 deepHashCode 를 사용하면, 쉽게 같은 배열인지 구별할 수 있다.
     *
     * 단, int 배열을 사용할 수는 없고 래퍼클래스인 Integer[] 를 이용해야한다.
     */
    static int searchPath(int[] input) {
        // 배열을 복사해둔다. => 정렬할 배열을 별도로 만들어둔다. 이것은 비교 대상이 된다.
        int[] sorted = input.clone();
        // 기존의 배열을 정렬한다.
        Arrays.sort(sorted);

        // 배열의 해시코드를 key 값으로 사용하고, value는 해당 정점(뒤집은 배열)까지의 깊이를 의미한다.
        Map<Integer, Integer> discovered = new HashMap<>();
        // 방문 예정인 정점 (발견한 배열)을 저장하는 저장 공간
        // 너비 우선 탐색을 가능하게 해주는 자료형은 FIFO 구조를 가진 Queue를 사용해야한다.
        Queue<int[]> queue = new LinkedList<>();

        // 시작 시점을 집어 넣는다.
        queue.add(input);
        discovered.put(hash(input), 0);

        // 너비 우선 탐색 시작
        // 방문할 정점이 있으면
        while (!queue.isEmpty()) {
            // 방문할 정점(배열)을 꺼낸다.
            int[] here = queue.poll();
            // 발견한 배열의 해시코드 값
            int key_here = hash(here);

            // 정렬된 배열과 동일한 배열을 찾으면 반복을 멈춘다.
            if (Arrays.equals(here, sorted)) {
                return discovered.get(key_here);
            }

            // 가능한 모든 부분을 뒤집어 본다.
            for (int i=0; i<here.length; i++) {
                // 크기 2 이상부터 시작
                for (int t=i+2; t<=here.length; t++) {
                    // 배열을 뒤집기 전에 복사본을 만들어 놓음
                    int[] copy = here.clone();

                    // 뒤집은 copy 배열 => 새로 만든 배열
                    reverse(copy, i, t);
                    // 새로 발견한 배열의 키값
                    int key_there = hash(copy);

                    // 새로운 베열 copy가 기존에 없던 배열이면
                    if (!discovered.containsKey(key_there)) {
                        // 깊이
                        int deep = discovered.get(key_here);
                        // 발견한 배열
                        queue.add(copy);
                        // here 배열(copy 아님) 탐색 완료
                        discovered.put(key_there, deep + 1 );
                    }
                }
            }
        }

        return -1;
    }

    /**
     * 배열을 디버깅 하기 위해 사용합니다.
     * */
    static void toString(int[] arr) {
        System.out.print("{");
        for (int i=0; i<arr.length; i++) {
            System.out.print(arr[i]);
            if (i + 1 < arr.length) {
                System.out.print(",");
            }
        }
        System.out.println("}");
    }

    /**
     * 배열의 해시코드 값을 반환합니다.
     * 같은 배열의 경우, 같은 해시 코드값을 반환합니다.
     * */
    static int hash(int[] arr) {
        return Arrays.deepHashCode(Arrays.stream(arr).boxed().toArray(Integer[]::new));
    }

    /**
     * 배열의 일부분 또는 전체를 뒤집는 방법
     *
     * reverse(arr, 0, 3) 은
     * 배열 arr의 0번 부터 2번(3번 앞) 까지의 배열을 뒤집습니다.
     * */
    static void reverse(int[] arr, int s, int e) {
        int[] copy = Arrays.copyOfRange(arr, s, e);

        int len = copy.length;
        for (int i=0; i<len; i++) {
            arr[s+i] = copy[len - (i+1)];
        }
    }
}

 

출력 1 & 결과

public static void main(String[] args) {
    int[] input1 ={1,2,3,4,8,7,5,6};
    int[] input2 ={1,2,3,4,8,7,6,5};
    int[] input3 ={3, 9999, 1, 2};
    int[] input4 ={1000, 2000, 3000};

    System.out.println(searchPath(input1)); // 2
    System.out.println(searchPath(input2)); // 1
    System.out.println(searchPath(input3)); // 2
    System.out.println(searchPath(input4)); // 0
}

 

 

문제점

위 풀이에서, 정렬해야하는 배열의 크기가 n이라고 하면 최악의 경우
n! (factorial) 개의 정점을 탐색해야 합니다.
n이 8 이라고 하면 40320 개의 정점을 탐색합니다.
테스트 케이스가 1000건이라고 했으니
최악의 경우 40320 * 1000 => 40320000 번의 탐색을 해야하기 때문에 테스트 케이스를 시간안에 푸는 것은 어렵습니다.

따라서 아래와 같이 두가지를 적용해서 프로그램을 수십 배 더 빠르게 할 수 있습니다.


1. 미리 계산해두기
정렬이 되어 있지 않은 배열을 뒤집어 가면서 정렬 된 배열을 찾아가는 과정이 아니라
미리 정렬 된 배열을 뒤집어 계산해두고, 받은 배열을 키로 변환해서 계산된 값에서 꺼내오는 오면 된다. 

2. 받은 배열을 상대값으로 변환해두기.
예를 들어 {10, 20, 30, 9999} 는 {0,1,2,3} 으로 변환해도 똑같은 결과가 나옴

{1,2,4,3}을 뒤집은 것은 {10, 20, 40, 30}을 뒤집은 것과 똑같은 회수로 뒤집어야 하기 때문에
받은 배열을 상대크기(순열)로 만든 배열인 {1,2,4,3}를 사용해도 된다.


배열을 뒤집어 가면서, deep(깊이=뒤집은 회수)을 미리 계산 해놓는다.

=> 1000건의 케이스를 테스트 하는 실제 알고리즘 테스트에서 static으로 결과를 미리 만들어 놓고
키(배열) 값으로 deep(깊이)을 찾아온다.

 

풀이 2

public class two {

    // 배열을 해시화 해서 키값으로 사용,
    static Map<Integer, Integer> discovered = new HashMap<>();

    static void preCalc(int n) {
        int[] perm = new int[n];
        for (int i=0; i<n; i++) {
            // 정렬된 배열 생성
            perm[i] = i;
        }

        // 방문할 정점(배열)을 저장할 공간 => 재귀 호출이 아닌, Queue 를 사용해서 저장하는 것이 핵심
        Queue<int[]> queue = new LinkedList<>();

        // 큐에 탐색할 대상을 넣어둔다.
        queue.add(perm);
        discovered.put(hash(perm), 0);

        // 탐색 시작
        while (!queue.isEmpty()) {
            // 배열을 꺼내옴
            int[] here = queue.poll();
            // 배열을 뒤집기 전에 미리, 해시값으로 변환하여, discovered에 저장된 깊이를 찾아옴
            int cost = discovered.get(hash(here));

            for (int i=0; i<n; i++) {
                // 2 크기 이상 부터 시작
                for (int j=2+i; j<=n; j++) {
                    int[] copy = here.clone();

                    // 뒤집은 copy 배열
                    reverse(copy, i, j);

                    int there = hash(copy);
                    // 새로운 베열이 발견 되지 않았으면
                    if (!discovered.containsKey(there)) {
                        // 이 때 복사본을 넣어야함
                        queue.add(copy);
                        discovered.put(there, cost + 1);
                    }

                    // reverse(here, i, j);
                }
            }

        }
    }

    /**
     * 받은 배열 값을 상대값으로 변환된 배열을 통해,
     *
     * 탐색한 값을 찾아온다.
     * */
    static Integer solve(int[] perm) {
        // perm 을 [0, ...,n-1] 의 순열로 변환한다.
        int n = perm.length;
        int[] fixed = new int[n];

        // 배열 전체 반복
        for (int i=0; i<n; i++) {
            int smaller = 0;

            // 기준이 되는 값보다 작은 값이 많을 수록 상대값이 +1 된다.
            for (int j=0; j<n; j++) {
                if (perm[j] < perm[i])
                    ++smaller;
            }

            fixed[i] = smaller;
        }

        return discovered.containsKey(hash(fixed)) ? discovered.get(hash(fixed)) : -1;
    }

    /**
     * 해시코드로 변환
     * 값이 같은 배열은 같은 해시코드를 반환
     * */
    static Integer hash(int[] arr) {
        return Arrays.deepHashCode(Arrays.stream(arr).boxed().toArray(Integer[]::new));
    }

    /**
     * 배열의 일부분 또는 전체를 뒤집는 로직
     * */
    static void reverse(int[] arr, int s, int e) {
        int[] copy = Arrays.copyOfRange(arr, s, e);

        int len = copy.length;
        for (int i=0; i<len; i++) {
            arr[s+i] = copy[len - (i+1)];
        }
    }

    /**
     * 배열을 디버깅 할 때 사용
     * */
    static void toString(int[] arr) {
        System.out.print("{");
        for (int i=0; i<arr.length; i++) {
            System.out.print(arr[i]);
            if (i + 1 < arr.length) {
                System.out.print(",");
            }
        }
        System.out.println("}");
    }
}

 

출력 2 & 결과

public static void main(String[] args) {
    // 두 배열을 자세히 보면 좀 다릅니다
    int[] input1 ={1,2,3,4,8,7,5,6};
    int[] input2 ={1,2,3,4,8,7,6,5};

    // 미리 계산
    preCalc(input2.length);

    int value1 = solve(input2);
    int value2 = solve(input1);

    System.out.println(value1); // 1
    System.out.println(value2); // 2
}

 

 

개인적으로 Java와 C는 다르게 동작하기 때문에

특히 배열을 키 값으로 사용해야하는 부분에서 애를 먹었습니다.

배열을 자료구조에 저장할 경우 키값으로 접근한다는 사실을 잊지말고 푸시면 훨씬 수월하실 겁니다.