[백준] 21315 카드 섞기 java

문제

마술사 영재는 카드 더미를 이용한 마술을 개발하였다.

카드들에는 1부터 N까지의 숫자가 적혀있으며 초기 상태에는 1이 맨 위에 있으며 N개의 카드가 번호 순서대로 쌓여있다.

영재는 마술을 위해 (2, K) - 섞기를 만들었다.

(2, K) - 섞기는 총 K + 1개의 단계로 이루어져있다.

첫 번째 단계는 카드 더미 중 밑에서 2K개의 카드를 더미의 맨 위로 올린다.

이후 i(2 ≤ i ≤ K + 1)번째 단계는 직전에 맨 위로 올린 카드 중 밑에서 2K - i + 1개의 카드를 더미의 맨 위로 올린다.

예를 들어, 카드의 개수가 5개 일 때 초기 상태에서 (2, 2) - 섞기를 하는 과정은 다음과 같다.(괄호 내에서 왼쪽에 있을수록 위에 있는 카드이다.)

• (1, 2, 3, 4, 5) → (2, 3, 4, 5, 1) → (4, 5, 2, 3, 1) → (5, 4, 2, 3, 1)

영재의 마술은 상대방이 초기 상태에서 (2, K) - 섞기를 2번 한 결과를 보고 2번의 (2, K) - 섞기에서 K가 각각 무엇인지 맞추는 마술이다.

마술 아이디어는 생각했지만, K를 알아내는 방법을 모르는 영재를 위해 K를 알아내는 프로그램을 만들자.

2번의 (2, K) - 섞기 후의 카드 더미 결과를 만드는 각각의 K는 유일함이 보장된다.

입력

첫 줄에 N이 주어진다.

둘째 줄에 2번의 (2, K) - 섞기 후의 카드 더미가 위에 있는 카드부터 공백으로 구분하여 주어진다.

출력

첫 번째 K와 두 번째 K를 출력한다.

제한

• 3 ≤ N ≤ 1,000
• 1≤ K, 2K < N

풀이

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int n, k, k1, k2;
    static int[] input;
    static int[] deck;

    public static void main(String[] args) throws IOException {
        init();
        solve();
        System.out.println(k1 + " " + k2);
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        deck = new int[n];
        input = new int[n];
        for(int i = 0; i < n; i++) {
            input[i] = Integer.parseInt(st.nextToken());
            deck[i] = i+1;
        }
    }

    static void solve() {
        for(int i = 1; Math.pow(2,i) < n; i++) {
            for(int j = 1; Math.pow(2,j) < n; j++) {
                int[] arr = deck.clone();
                shuffle(i, arr);
                shuffle(j, arr);
                boolean flag = true;
                for(int k = 0; k < n; k++) {
                    if(arr[k] != input[k]) {
                        flag = false;
                        break;
                    }
                }
                if(flag) {
                    k1 = i;
                    k2 = j;
                    return;
                }
            }
        }
    }

    static void shuffle(int k, int[] arr) {
        int range = n;
        int cnt;
        for(int i = 1; i <= k+1; i++) {
            cnt =(int)Math.pow(2, k-i+1);
            swap(range,cnt, arr);
            range = cnt;
        }
    }

    static void swap(int range, int cnt, int[] arr) {
        List<Integer> tmp = new ArrayList<>();
        //2^k-i+1개의 카드를 임시 배열에 옮기기
        for(int i = range-cnt; i < range; i++) {
            tmp.add(arr[i]);
            arr[i] = 0;
        }
        //임시 배열로 옮긴 원소들을 맨위로 옮기기
        for(int i = 0; i < n; i++) {
            if(arr[i] != 0) {
                tmp.add(arr[i]);
            }
            arr[i] = tmp.get(i);
        }
    }
}

처음부터 문제이해가 되지 않아서 (?) 얼마 없는 다른 사람의 풀이를 보고 겨우 이해한 문제이다. 

 

문제만 이해하면 풀이 자체는 단순히 완전탐색을 하면 되는 문제이고 배열 안에서 일정 범위의 값들의 스위칭을 어떻게 구현할 것인지가 중요한 문제였다.

 

문제를 보면 2번의 (2,k)-섞기를 한 값이 입력으로 들어온 수열과 같은 첫번 째 k값과 두번 째 k값을 구하는 것인데 우선 k의 범위부터 정의 하자면 1 <= 2^k < n 이다. 만약 n이 5라면 가능한 k의 범위는 1 ~ 2 이다.

 

그렇다면 중복 순열로 모든 경우의 수를 탐색할 수 있는데 2개만 뽑으면 되니 2중 for문으로 구현이 가능하다.

 

(2,k)-섞기의 구현은 임시 리스트 하나를 만들어서 직전 맨위로 올린 카드들 중 밑에서부터 2^k-i+1 개의 카드를 임시 리스트에 넣어주고 배열에는 0표시를 한다. 그리고나서 배열의 처음부터 탐색하며 0이 아닌 부분은 임시 리스트의 뒤에 넣어주고 해당 위치에 임시 배열의 같은 위치에 있는 원소를 넣어주면 된다.