[JAVA] BOJ(백준) - 카드 섞기 - 21315

문제내용

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

21315번: 카드 섞기

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

카드들에는 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

---

문제풀이

이미 2번 섞인 카드들을 보고 거꾸로 한번에 되찾아 갈수 있는 방법은 없다(적어도 필자 머릿속엔 방법이 없음..).

따라서 카드의 초기상태에서 k를 2개 뽑아 2번 섞은 결과가 입력값과 같은지 확인해봐야 한다.

 

그래서 필자는 백트래킹을 이용해 1~n까지 숫자중 2개를 뽑아 k를 2개 만들었다.

이후엔 문제에서 주어진대로 섞는걸 구현해 내고, 결과가 입렵값과 같은지만 확인하면 된다.

즉, 완전탐색을 통해 결과값을 확인하라는 얘기다.

 

근데 여기서 필자가 좀 헷갈렸던건... 문제의 마지막에 "카드 더미 결과를 만드는 각각의 K는 유일함이 보장된다."

라는 말이있다. 이말을 보고 2개의 k는 같은 숫자로 중복이 되면 안되구나 라고 생각했는데 그게 아니다. 중복된다.

 

그래서 만약 n=5 라고 한다면,

k = ( 1, 1 ) ( 1, 2 ) ( 2, 1) (1, 1) 이렇게 총 4가지 경우를 다 확인 해야한다.

 

구현 과정에는 여러가지 방식이 있겠지만 필자는 다음과 같이 풀었다.

 

1. 섞이는 카드수를 cnt에 저장한다.

2. 섞이는 카드 기준으로 왼쪽에 있는 카드 수들을 left 변수에, 오른쪽에 있는 카드 수들을 right 변수에 저장한다.

3. 이후 leftList , rightList 두가지 임시리스트를 만들어서 add,poll을 활용해 카드를 섞어 준다.

 

즉, n=5 이고 k=2 이라면

1단계(1단계는 뒤에서부터 빼고 앞에 넣으면 돼서 cnt만 있어도됨)

cnt = 4 :    1 2 3 4 5  -> 2 3 4 5 1

 

2단계

cnt = 2, left = 2, rigth = 1 :     2 3 4 5 1 -> leftList = ( 2, 3 ) , rightList = ( 1 ) -> 4 5 2 3 1

 

3단계

cnt = 1, left = 1, right - 3 :     4 5 2 3 1 -> leftList  = ( 4 ) , rightList = ( 1, 3, 2 ) -> 5 4 2 3 1

(rightList에선 pollLast로 저장해놨기 때문에 카드를 다시 list에 넣어줄때도 pollLast로 넣어준다 / LIFO 개념)

 

코드를 보자.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static String target=""; //최종적으로 나와야하는 카드순서
	static int n; //카드개수
	static LinkedList<Integer> list; //섞고나서 카드를 저장할 리스트
	static StringBuilder ans = new StringBuilder(); //정답
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++)  
			 target += st.nextToken();
		
		
		//1단계 = 2^k
		//...
		//i단계 = 2^(k-i+1)
		StringBuilder sb = new StringBuilder();
		dfs(0,sb);
		
		
	}
	
	//depth:카드섞을 횟수, sb:k의 종류
	public static void dfs(int depth, StringBuilder sb) {
		if(depth==2) {
			int k1=sb.charAt(0)-'0', k2=sb.charAt(1)-'0';
			
			//리스트 초기화
			list = new LinkedList<Integer>();
			for(int i=0; i<n; i++)
				list.add(i+1);
			
			mix(k1);//섞기
			mix(k2);//섞기
			
			for(int l:list) 
				ans.append(l);
			
			if(!ans.toString().equals(target)) ans.setLength(0);
			else {
				System.out.println(k1+" "+k2);
				System.exit(0);
			}
			
			return;
		}
		
		//조합으로 k를 다뽑음
		for(int i=1; i<n; i++) {
			if(i>=n || (int) Math.pow(2, i)>=n) continue;//제한조건
			sb.append(i);
			dfs(depth+1,sb);
			sb.delete(sb.length()-1, sb.length());
		}
	}
	
	public static void mix(int k) {
		//cnt: 섞일 카드수
		int cnt = (int) Math.pow(2, k);
		
		firstStep(cnt); //1단계
		NStep(k,cnt,2,k-1); //n단계
	}
	
	public static void firstStep(int cnt) {
		while(cnt-->0) {
			int num = list.pollLast();
			list.addFirst(num);
		}
	}
	
	//pre:이전에 섞은 카드수, i:단계, limit:k-i+1
	public static void NStep(int k, int pre, int i, int limit) {
		while(limit>=0) {
			int cnt = (int) Math.pow(2, limit);//섞일 카드수
			int left = pre - (int) Math.pow(2, limit);//섞일 카드들 기준으로 왼쪽에 있는 카드들
			int right = list.size() - pre;//섞일 카드들 기준으로 오른쪽에 있는 카드들
			
			LinkedList<Integer> leftList = new LinkedList<Integer>();//왼쪽카드들 저장해줄 임시리스트
			LinkedList<Integer> rightList = new LinkedList<Integer>();//오른쪽카드들 저장해줄 임시리스트
			
			//카드 임시저장
			while(left-->0) 
				leftList.add(list.poll());
			while(right-->0) 
				rightList.add(list.pollLast());
			
			//저장했던 카드들을 list에 순서에 맞게 담아주기.
			while(!leftList.isEmpty()) 
				list.add(leftList.poll());
			while(!rightList.isEmpty())
				list.add(rightList.pollLast());
			
			//변수값 갱신
			pre = cnt;
			i++;
			limit = k-i+1;
		}
	}
}

---

마치며

솔직히 내가 짠 코드가 좋은 코드인가 라고 물어본다면 다른 효율적인 코드가 존재하기에 그렇게 말할 순 없다. 그래도 풀었다는 의미가 있고 코드 소스가 많아서 이해하기가 더 쉽지 않을까 생각한다.