Absolute Permutation

문제: Absolute Permutation

난이도: Medium

 

문제 설명

 n과 k(n은 0보다 큰 정수, k는 0보다 크거나 같은 정수)가 주어졌을 때 1부터 n까지의 정수가 하나씩 들어있는 배열 P의, 사전 순으로 가장 작은 absolute permutation을 구하라. 만약 P의 absolute permutation이 없다면 값이 -1만 있는 배열을 리턴하라.

 absolute permutation은 배열의 모든 값과 그 값의 자리값(1부터 n까지)의 차의 절대값이 모두 k인 배열을 뜻한다. 예를 들어, n=4, k=2일 경우 P의 absolute permutation은 [3, 4, 1, 2]이다(3의 자리값은 1, 4의 자리값은 2, 1의 자리값은 3, 2의 자리값은 4 이므로 모두 차의 절대값이 2이다).

 

문제 해결

소스 코드

static int[] absolutePermutation(int n, int k) {
        int[] arr = new int[n];
        int[] minus = {-1};
        int slice = 0;
        
        if(k==0) {
            for(int i = 1; i <= n; i++) {arr[i-1] = i;}
            return arr;
        }

        if(n%2==1||n/2<k||n%k!=0||(n/k)%2==1) {return minus;}

        for(int i = 0; i < n/(k*2); i++) {
            for(int j = 0; j < k; j++) {
                arr[slice+j] = j+slice+k+1;
                arr[slice+j+k] = j+slice+1;
            }
            slice += (2*k);
        }
        return arr;
    }

 

 

해설

 n과 k를 작은 수부터 임의로 지정해서 absolute permutation을 구해보는 것을 반복해 보면, absolute permutation에는 일정한 규칙이 존재한다는 것을 눈치챌 수 있다. 그 규칙은 다음과 같다.

 

1. n이 홀수인 경우, k=0일 경우에만 absolute permutation이 존재한다.
2. n/2가 k보다 작으면 absolute permutation이 없다.
3. n이 k로 나누어 떨어지지 않으면 absolute permutation이 없다.
4. n을 k로 나눈 몫이 홀수라면 absolute permutation이 없다.

k=0인 경우 absolute permutation은 1부터 n까지의 정수가 순서대로 있는 배열이다. k가 0이 아니고, absolute permutation이 존재하는 것으로 확인되었다면 위의 코드에 있는 규칙으로 absolute permutation을 구할 수 있다.