Larry's Array

문제: Larry’s Array

난이도: Medium

 

문제 설명

 1부터 값이 1씩 증가한 요소들로 이루어진 배열이 있다. 이 배열의 요소를 다음과 같은 방법으로 위치를 바꿀 경우 배열을 오름차순으로 정렬하는 것이 가능한가를 판별하여라.

ABC -> BCA -> CAB -> ABC

 배열 A가 {1, 6, 5, 2, 4, 3}일 경우는 다음과 같다.

문제 해결

소스 코드

static String larrysArray(int[] A) {
        int cnt = 0;
        String result = "";

        for(int i = 0; i < A.length-1; i++) {
            for(int j = i+1; j < A.length; j++) {
                if(A[i]>A[j]) {
                    cnt++;
                }
            }
        }

        if(cnt % 2 == 0) {
            result = "YES";
        } else {
            result = "NO";
        }

        return result;
    }

 

해설

 이 문제는 ‘15퍼즐 문제’에 대해 알고 있어야 풀이가 가능하다. 나는 몰라서 어떻게든 배열의 값들을 정렬해서 해결하려 했다가 실패했다.

 

15퍼즐 문제란, 누구나 한 번쯤 본적이 있을 숫자 정렬 퍼즐 에서 위의 그림과 같이 퍼즐의 숫자 14와 15의 위치만 바꾸는 것으로도 절대로 퍼즐을 풀 수 없게 된다는 문제이다.

 자신보다 자리값이 큰 위치에 있고 자신보다 작은 수의 개수를 f(n)이라고 하고, 모든 f(n)의 합을 X라고 하면 1부터 15까지 정렬된 퍼즐은 X = 0이다. 14와 15의 위치가 바뀐 경우는 X = 1 이다.

 

 이 퍼즐의 빈칸으로 숫자를 이동시킬 경우 가로, 세로 방향일 때는 X값의 변화가 없다. 상하 방향으로 이동시킬 경우에는 X값이 홀수만큼 증가하거나 감소한다. 이 때 빈칸의 위치도 홀수만큼 증감하므로 총 변화량은 짝수가 된다. 이렇게 15퍼즐은 숫자 이동시의 변화량이 반드시 짝수이고, 14와 15의 위치를 바꾼 퍼즐은 X가 홀수이므로 절대로 풀 수가 없게 되는 것이다.

 

 이 문제의 경우도 숫자 위치를 변화시킬 때의 변화량이 짝수이므로 X의 값이 짝수인가 아닌가를 체크하면 결과를 구할 수 있게 된다.