[BOJ - JAVA] 21315 - 카드 섞기 (브루트포스)

# 주소

https://www.acmicpc.net/problem/21315

21315번: 카드 섞기

# 문제

# 문제 해설 및 코드 리뷰

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main{
    static int n;
    static int[] arr;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n + 1];
        for(int i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        for(int i = 0; i <= 9; i++){
            if(Math.pow(2,i) >= n)
                break;
            for(int j = 0; j <= 9; j++){
                if(Math.pow(2,j) >= n)
                    break;
                Queue<Integer> queue = new LinkedList<>();
                for(int k = n; k >= 1; k--)
                    queue.add(k);
                dfs(i, queue);
                dfs(j, queue);
                boolean isOk = true;
                for(int k = n - 1; k >= 0; k--){
                    if(arr[k] != queue.poll()){
                        isOk = false;
                        break;
                    }
                }
                if(isOk){
                    System.out.println(i + " " + j);
                    return;
                }
            }
        }
    }
    static void dfs(int x, Queue<Integer> queue){
        Queue<Integer> temp = new LinkedList<>();
        int num = (int)Math.pow(2,x);
        for(int i = 0; i < num; i++)
            temp.add(queue.poll());
        while(num > 1){
            num /= 2;
            for(int i = 0; i < num; i++)
                temp.add(temp.poll());
            for(int i = 0; i < num; i++)
                queue.add(temp.poll());
        }
        queue.add(temp.poll());
    }
}

브루트포스 문제입니다.

저는 Queue를 이용해서 풀었습니다.

간단히 해설하자면, k가 입력되면 k+1단계 만큼 뒤섞기가 일어나는데 arr의 뒤에 있는 인덱스부터 2^k개만큼 앞으로 갑니다.

그러므로 Queue를 사용해야만 합니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n + 1];
for(int i = 0; i < n; i++)
    arr[i] = scan.nextInt();

살펴봅시다.

arr를 0부터 n-1열까지 저장받습니다.

for(int i = 0; i <= 9; i++){
    if(Math.pow(2,i) >= n)
        break;
    for(int j = 0; j <= 9; j++){
        if(Math.pow(2,j) >= n)
            break;

2중 for문으로 i와 j를 0부터 9까지 탐색해야합니다.

왜냐하면 2의 거듭제곱이 n보다 크거나 같아지면 탐색할 이유가 없기 때문인데요.

2의 0제곱은 1이기 때문에 0부터 2^9인 512까지 n의 크기가 정해져야 합니다.

(n은 1000까지라고 입력 제한되어 있습니다.)

그리고 Queue에 숫자를 담아야 하기 때문에 Queue를 선언하고 값을 넣겠습니다.

Queue<Integer> queue = new LinkedList<>();
for(int k = n; k >= 1; k--)
    queue.add(k);

queue에는 모든 정수를 순서대로 넣습니다. 

k부터 내림차순으로 넣게되면 queue에는 k, k - 1, k - 2, ... , 1까지 들어가게 되겠습니다.

그리고 dfs문을 2번 실행할텐데, queue를 넣어서 실행해봅시다.

dfs(i, queue);
dfs(j, queue);

dfs내부 구조는 다음과 같습니다.

static void dfs(int x, Queue<Integer> queue){
    Queue<Integer> temp = new LinkedList<>();
    int num = (int)Math.pow(2,x);
    for(int i = 0; i < num; i++)
        temp.add(queue.poll());
    while(num > 1){
        num /= 2;
        for(int i = 0; i < num; i++)
            temp.add(temp.poll());
        for(int i = 0; i < num; i++)
            queue.add(temp.poll());
    }
    queue.add(temp.poll());
}

파라미터로는 x와 queue를 담을 것입니다.

특히 queue를 새로운 temp라는 자료구조로 선언을 하여 임시로 숫자를 넣었다 뺐다 하기 위해 선언했습니다.

num = (int) Math.pow(2,x)라고 선언했는데, Math.pow의 타입은 double형이기 때문에 int로 형변환 시켰습니다.

원래는 로직 짤 때 범위를 Math.pow(2,x)를 다른 것으로 치환 안하고 사용하려다 너무 복잡해져서 치환하기로 했네요.

어쨌든, temp에는 num의 크기만큼 값을 넣어줄 것입니다.

만약 queue에는 [5, 4, 3, 2] 가 들어있다면 temp에도 [5, 4, 3, 2]가 입력될 것입니다.

그리고 while문을 이용하여 num을 계속 2로 나누면서 뒤섞기를 진행해보겠습니다.

제일 먼저, temp에는 2가 나눈 채로 진행이 될 것인데, K = 2일 때로 가정했다면 num은 2입니다.

그러므로 temp = [5, 4, 3, 2]일 때

for(int i = 0; i < num; i++)
    temp.add(temp.poll());
for(int i = 0; i < num; i++)
    queue.add(temp.poll());

이 로직에서, 첫 번째 for문에서 temp = [3, 2, 5, 4]가 되고 두 번째 for문에서

queue = [1, 3, 2]이고 temp = [5, 4]가 남습니다.

그리고 다시 돌아서 num = 1이 되고 for문을 돕니다.

이 때 temp에는 5가 뒤로 이동해서 temp = [4, 5]가 됩니다.

두 번째 for문에서 queue에는 4가 삽입되어 queue = [1, 3, 2, 4]가 될테고 temp = [5]만 남습니다.

마지막으로 while문 밖으로 빠져나오게 되고 queue에는 5가 더해져 queue 는 [1, 3, 2, 4, 5]가 될 것입니다.

이 과정을 한 번 더 거쳐서 원래의 arr값이 되는지 보는 것이 목적인데요.

그 뒤의 구문을 보시면

boolean isOk = true;
for(int k = n - 1; k >= 0; k--){
    if(arr[k] != queue.poll()){
        isOk = false;
        break;
    }
}

isOk를 true로 초기화하여 arr값이 queue.poll()의 값과 비교를 통해 만약 다르면 즉시 break를 걸어 시간낭비를 하지 않게 짭니다.

그리고 isOk가 true가 되면 i와 j를 출력하면 정답이 되겠습니다.

감사합니다.

 

Queue에 값을 넣었다 뺐다 하는게 어려워서 시간을 많이 잡아 먹었습니다.

Deque을 활용할까 하다가 Queue로 했는데 Deque으로 해도 상관은 없을 것 같았습니다.

(int) Math.pow(2,x)이 부분을 num으로 치환하고 할 걸 괜히 for문에 그대로 써서 하다가 코드만 길어지고 제가 풀던 거에 제가 헷갈리더군요. ㅠㅠ