ShuffleMethod

Code

public class ShuffleMethod

{

    int n;

    int[] ts;

    boolean[] flag;

    int[] sn;                  // selected number

    int[][] pn;                // possible number

    boolean visit(int cnt) {

        for (int i = 0; i < n; i++) {

            if (flag[i+1]) continue;

            for (int j = 0; j < pn[i].length; j++) {

                if (flag[pn[i][j]]) continue;

                sn[i] = pn[i][j];

                flag[sn[i]] = true;

                int a = sn[i]-1;

                int b = i;

                int cnt1 = cnt+1;

                boolean[] used = new boolean[n];

                for (int k = 0; k < pn[a].length; k++) {

                    if (flag[pn[a][k]] || pn[a][k]!=ts[b] || sn[a]!=0) continue;

                    sn[a] = ts[b];

                    flag[sn[a]] = true;

                    used[a] = true;

                    cnt1++;

                    if (cnt1 == n) return true;

                    b = a;

                    a = sn[a]-1;

                    k = -1;

                    if (ts[b] == sn[a]) return visit(cnt1);

                }

                flag[sn[i]] = false;

                for (int k = 0; k < n; k++)

                    if (used[k]) {flag[sn[k]] = false; sn[k] = 0;}

            }

        }

        return false;

    }

    public int[] oneTime(int[] twoShuffle) {

        n = twoShuffle.length;

        ts = twoShuffle;

        flag = new boolean[n+1];

        sn = new int[n];

        int cnt = 0;

        for (int i = 0; i < n; i++) {

            if (i+1 == ts[i]) {

                flag[i+1] = true;

                sn[i] = i+1;

                cnt++;

            }

        }

        if (cnt == n) return sn;

        pn = new int[n][n-2-cnt];

        for (int i = 0; i < n; i++) {

            if (flag[i+1]) continue;

            for (int j = 0, k = 0; j < n; j++) {

                if (i==j || j+1==ts[i] || flag[j+1]) continue;

                pn[i][k++] = j+1;

            }

        }

        if (visit(cnt)) return sn;

        return new int[0];

    }

}

Explanation

카드 입력과 카드 결과를 비교해 중간 번호를 찾아내면 된다. 입력과 결과에 있는 같은 색인에 있는 카드 번호가 일치하면, 같은 자리끼리 섞었다는 뜻이므로 바꾸지 않아도 된다

예)

초기값: 1 2 3 4

중간값: ? ? ? ?

결과값: 4 3 2 1

위 숫자들에서 중간값 첫번째 자리에는 1과 4는 올 수 없고 2,3만이 올 수 있다. shuffle한 결과값이 1이 아닌 4이기 때문에 shuffle이 되지 않았거나 같은 자리끼리 shuffle됐기 때문이다.

지엽적인 부분만 섞어질 경우가 존재하므로 visit()을 다시 호출해 남은 카드를 찾으면 된다.

예)

첫줄(초기값): 초기 카드,    둘째줄(중간값): 한 번 섞은 카드,    셋째줄(결과값): 두 번 섞은 카드

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
3	6	2	8	9	4		5	1		11
2	4	6	5	1	8	10	9	3	12	11	13	7	15	16	17	14

위 표의 9번에 중간값 1이 있다. 따라서 1번에 9번의 결과값을 넣어주면 3이 들어간다. 문제는 1번의 중간값이 3이고 따라서 3번에 1번의 결과값인 2를 집어넣어야 하는데 이미 2를 이전에 집어넣었다. 즉, 계속 순환하는 문제가 발생하므로 새롭게 함수를 호출해야 한다.