[BOJ] 1091 카드섞기 - JAVA

1. 문제

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

1091번: 카드 섞기

3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번)

0번째 위치에 있던 카드가 플레이어 0에게 가고, 1번째 위치에 있던 카드는 플레이어 1에게 가고, 2번째 위치에 있던 카드는 플레이어 2에게 가고, 3번째 위치에 있던 카드는 플레이어 0에게 가고, 이런식으로 카드를 나누어 준다.

카드가 섞이는 방법 - 길이가 N인 수열 S. 카드를 한 번 섞고 나면 i번째 위치에 있던 카드는 S[i]번째 위치로 이동

각 카드가 어떤 플레이어에게 가야 하는지에 대한 정보 - 길이가 N인 수열 P. 맨 처음 i번째 위치에 있던 카드를 최종적으로 플레이어 P[i] 에게 보내야한다.

지민이가 목적을 달성하기 위해 필요한 카드 섞는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

---

2. 풀이

1.  입력

- 25번째 줄까지 전부 입력부분이다. 처음의 카드 상태와 비교하기 위해 cards배열을 복사해서 compare에 넣어놓았다.

 

2.  탐색

- cards가 p와 같거나 result가 0이 아니면서 cards와 처음상태인 compare가 같다면 싸이클이 끝난것이므로 종료한다.

- 순서배열에 인덱스값을 넣어놓았으므로 그 값에 맞춰서 다음 배열을 만든다. 원본유지가 필요해서 next에 저장하다가 마지막에 cards를 교체했다. 교체하면 result는 +1한다.

 

3.  출력

- 만약 result가 0이 아니면서 cards와 compare가 같다면 한 사이클이 끝났는데도 답을 찾지 못한 경우다. 따라서 -1을 출력한다.

- 그 외의 경우에는 답을 출력한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_1091_카드섞기 {
   public static void main(String[] args) throws Exception {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      
      int N = Integer.parseInt(in.readLine());
      int[] p = new int[N];
      int[] order = new int[N];
      int[] cards = new int[N];
      
      StringTokenizer st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) p[i] = Integer.parseInt(st.nextToken());
      
      st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) {
         order[Integer.parseInt(st.nextToken())] = i;
         cards[i] = i%3;
      }

      int[] compare = cards.clone();
      int[] next = new int[N];

      int result = 0;
      while(!Arrays.equals(cards,p) && !(result !=0 && Arrays.equals(cards, compare))) {
         for(int j=0;j<N;j++) next[order[j]] = cards[j];
         
         cards = next.clone();
         result++;
      }
   
      if(result !=0 && Arrays.equals(cards, compare)) System.out.println(-1);
      else System.out.println(result);
   }
}

---

3. 결과

로직은 맞는 것 같은데 왜 메모리초과였는지 모르겠다.

초기 코드는 이랬다. 음... 초기상태와 비교하려고 5번째 줄에서 card%3과 비교한 게 문제였을까? 정말 모르겠다.

while(true) {				
    boolean stop = true;
    int count = 0;
	for(int card=0;card<N;card++) {
		if(cards[card]==card%3) ++count;
		if(p[card]!=cards[card]) {
			stop = false;
			break;
		}
	}
	if(stop) {
		System.out.println(result);
		break;
	}
	else if(count==N) {
		System.out.println(-1);
		break;
	}
	
	for(int j=0;j<N;j++) next[order[j]] = cards[j];
	
	cards = next.clone();
	result++;	
}