[백준/JAVA] 21315번: 카드 섞기

📖 문제

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

 

 

 

💡  풀이 방식

• 브루트포스

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K, K1, K2;
    static int[] input, deck;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        input = new int[N];
        deck = new int[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            input[i] = Integer.parseInt(st.nextToken());
            deck[i] = i+1;
        }
        
        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;
                    break;
                }
            }
        }
        
        System.out.println(K1 + " " + K2);
    }
    
    private static void shuffle(int k, int[] arr) {
        int range = N;
        int cnt = 0;
        
        for(int i = 1 ; i <= k+1 ; i++) {
            cnt = (int)Math.pow(2, k-i+1);
            swap(range, cnt, arr);
            range = cnt;
        }
    }
    
    private 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; // 배열에는 0 표시
        }
        
        // 임시 배열로 옮긴 원소들을 맨 위로 올리기
        for(int i = 0 ; i < N ; i++) {
            // 0이 아닌 부분은 임시 리스트 뒤에 넣기
            if(arr[i] != 0) {
                tmp.add(arr[i]);
            }
            // 해당 위치에 임시 배열의 같은 위치에 있는 원소 넣기
            arr[i] = tmp.get(i);
        }
    }
}
 

 

 

➕ 다른 풀이 방식

개인적으로 이게 더 이해하기 쉬웠당,, (출처 : https://www.acmicpc.net/source/78306893)

LinkedList를 사용하심

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;
    static LinkedList<Integer> list;    // 변형된 리스트
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 1 ; Math.pow(2, i) < N ; i++) {
            for(int j = 1 ; Math.pow(2, j) < N ; j++) {
                // 리스트에 1부터 N까지 숫자 추가
                list = new LinkedList<>();
                for(int x = 1 ; x <= N ; x++) {
                    list.add(x);
                }
                
                shuffle(i);    // i번 섞기
                shuffle(j);    // j번 섞기
                
                // 섞인 리스트가 주어진 배열과 같은지 확인
                if(chk()) {
                    System.out.println(i + " " + j);
                    return;
                }
            }
        }
    }
    
    // 리스트가 주어진 배열과 같은지 확인하는 함수
    private static boolean chk() {
        for(int i = 0 ; i < N ; i++) {
            if(arr[i] != list.get(i))
                return false;
        }
 
        return true;
    }
    
    // 리스트 섞는 함수
    private static void shuffle(int k) {
        int x = 1;    // 시작 인덱스
        
        // k번 반복
        while(k - x + 1 >= 0) {
            int cnt = (int)Math.pow(2, k-x+1);    // 2의 k-x+1 승
            
            // cnt번 반복
            for(int j = 0 ; j < cnt ; j++) {
                if(x == 1)    // 리스트의 마지막 요소를 첫 번째로 이동
                    list.addFirst(list.removeLast());
                else    // 2의 k-x+2 승 - 1 위치의 요소를 첫 번째로 이동
                    list.addFirst(list.remove((int)Math.pow(2, k-x+2) -1));
            }
            
            x++;    // 인덱스 증가
        }
    }
}
 

 

 

 

---

💦 어려웠던 점

- 원소를 스위칭하고 이걸 거꾸로??라는 생각에 차마 손을 대지 못 했다,,

 

🧐 새로 알게 된 내용

- ArrayList vs LinkedList의 차이. 삽입/삭제 시에는 LinkedList이 더 빠르다고 한다! (참고)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 21315 카드 섞기 java