[백준] 카드섞기 : 21315 - 완탐 (Java)
1. 문제
https://www.acmicpc.net/problem/21315
요약
카드를 2번 섞은 후에 결과를 줄테니, 각 2번의 k 값을 구해라
2. 접근
독해력이 안좋아서 문제 이해하기가 어려웠다. 아무튼 k의 값을 구하는 건데, 문제의 조건을 보면
- 3 ≤ N ≤ 1,000
- 1≤ K, 2K < N
로 k는 1~9의 값을 가질 것이다. 그리고 두 번만 수행하면 되니 최대 많아야 9*9 = 81번이니 완탐으로 접근한다.
최종 결과를 보고 처음 결과로 돌아가기(x)
처음엔 입력으로 주어진 결과를 이용하여 연산을 거꾸로 해서 초기값을 찾고자 했다. 하지만 좋은 방법이 아니였다. 연산이 더 복잡해지고 생각할 것이 많아진다.
처음상태를 가지고 최종 결과와 비교하기(o)
그래서 초기 값이 {1, 2, 3..., N} 순서로 주어진다니깐 이때 k값을 달리해서 2번 섞기로 했다. 사실 이 방법이 쉬운데 처음에는 떠오르지 않아서 해맸다.
카드 섞기 구현
섞는 방법은 문제에 그대로 나와있다. 하지만 어려웠다.
조건은 이전 작업 때 위로 올린 카드만을 이용한다는 점이다. 이 점 때문에 어려웠는데 이전에 올린 카드를 어떻게 구별하면 될까? 고민했고 떠오른 방법이 `Queue`라서 `Queue`를 사용하기로 했다.
핵심은 이전 작업 때 건들인 카드가 아니면 더 이상 이 카드는 섞이지 않으니, 결과를 저장하는 `base` 큐에 넣는 것이다. 그리고 섞은 카드는 임시 큐인 `temp`에 넣어서 이후 작업에는 `temp`에 담긴 카드만 활용했다.
private void mixCard(Queue<Integer> base, int k){
Queue<Integer> temp = new LinkedList<>();
// 밑에서 2^K개의 카드를 더미의 맨 위로 올린다.
for(int i=0; i<Math.pow(2, k); i++){
temp.offer(base.poll());
}
// i(2 ≤ i ≤ K + 1)번째 단계는 직전에 맨 위로 올린 카드 중 밑에서 2^(K - i + 1)개의 카드를 더미의 맨 위로 올린다.
for(int i=2; i<= k+1; i++){
int size = temp.size();
int cnt =0;
for(int c = 0; c< Math.pow(2, k-i+1); c++){
cnt++;
temp.offer(temp.poll());
}
// 아직 남아있는 거는 base로
while(cnt < size){
base.offer(temp.poll());
cnt++;
}
}
while (!temp.isEmpty()){
base.offer(temp.poll());
}
}
3. 전체 코드
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public int [] run(int N, int [] after){
// 2^k < N 을 만족하는 Max K
int maxK = getMaxK(N);
for(int i=1; i<=maxK; i++){
for(int j=1; j<=maxK; j++){
Queue<Integer> base = new LinkedList<>();
for(int n=N; n>=1; n--){
base.add(n);
}
mixCard(base, i);
mixCard(base, j);
int [] result = queToArray(base);
if(isSame(result, after)){
return new int[]{i,j};
}
}
}
return new int[2];
}
private boolean isSame(int [] arr1, int [] arr2){
for(int i=0; i<arr1.length; i++){
if(arr1[i] != arr2[i])
return false;
}
return true;
}
private int[] queToArray(Queue<Integer> base) {
int [] result = new int[base.size()];
for(int i=result.length-1; i>=0; i--){
result[i] = base.poll();
}
return result;
}
private void mixCard(Queue<Integer> base, int k){
Queue<Integer> temp = new LinkedList<>();
// 밑에서 2^K개의 카드를 더미의 맨 위로 올린다.
for(int i=0; i<Math.pow(2, k); i++){
temp.offer(base.poll());
}
// i(2 ≤ i ≤ K + 1)번째 단계는 직전에 맨 위로 올린 카드 중 밑에서 2^(K - i + 1)개의 카드를 더미의 맨 위로 올린다.
for(int i=2; i<= k+1; i++){
int size = temp.size();
int cnt =0;
for(int c = 0; c< Math.pow(2, k-i+1); c++){
cnt++;
temp.offer(temp.poll());
}
// 아직 남아있는 거는 base로
while(cnt < size){
base.offer(temp.poll());
cnt++;
}
}
while (!temp.isEmpty()){
base.offer(temp.poll());
}
}
private int getMaxK(int N){
int k= 0;
int cur = 1;
while(true){
cur *=2;
k++;
if(cur >= N){
break;
}
}
return k-1;
}
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(br.readLine());
String [] numStr = br.readLine().split(" ");
int [] nums = new int[numStr.length];
for(int i=0; i<nums.length; i++){
nums[i] = Integer.parseInt(numStr[i]);
}
// k는 1 ~ 9 까지. 81개의 경우
int [] resut = new Main().run(N, nums);
System.out.println(String.format("%d %d", resut[0], resut[1]));
}
}
4. 후기
구현력이 부족한 것 같다. 앞으로 구현 + 완탐 문제 좀 많이 풀어야겠다.