[BOJ] 15501 부당한 퍼즐 - JAVA

1. 문제

15501번: 부당한 퍼즐

현욱은 퍼즐 게임을 굉장히 좋아한다. 어느 날 현욱은 친구로부터 간단한 플래시 퍼즐 게임을 하나 추천 받았는데, 이 퍼즐 게임은 다음과 같은 규칙을 갖고 있다.

1. 플레이어는 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열을 하나 가지고 시작한다.
2. 또 다른 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열이 주어졌을 때, 처음 수열을 적절히 변형해서 처음 받은 수열을 이 수열과 동일한 수열로 만들어야 한다.
3. 이때, 플레이어가 수열에 대해서 할 수 있는 동작은 다음 두 가지가 있다. 동작은 몇 번이라도 수행할 수 있다.
- 뒤집기 : 현재 수열을 거꾸로 뒤집는다. ex) 1 2 3 4 5 -> 5 4 3 2 1
- 밀기 : 현재 수열을 왼쪽 혹은 오른쪽으로 한 칸 민다. ex) 1 2 3 4 5 -> 5 1 2 3 4

퍼즐을 풀던 현욱은 분명히 엄청 쉬운 규칙인데도 불구하고 문제가 안 풀려서, 한참을 고민하다가 다시 잘 비교해보니 정답 수열을 주어진 동작만으로는 절대 만들 수가 없는 문제였다!

화가 난 현욱은 퍼즐 제작자에게 따지기 위해 주어진 문제가 올바른 문제인지 아닌지 확인하는 프로그램을 만들기로 결심했다. 현욱을 도와 괘씸한 퍼즐 제작자를 응징해주자.

---

2. 풀이

1.  첫번째 수열을 input, 두번째 수열을 output에 저장한다.

2.  1~N까지 숫자가 하나씩만 존재하기 때문에 input[0]과 같은 숫자가 output에 어디있는지 찾은 후 그 숫자부터 역방향, 정방향으로 두 번 탐색하면 된다.

3.  %연산을 이용해서 정방향은 (i+idx)%N, 역방향은 (idx+N-i)%N으로 output배열 인덱스를 찾아 비교한다.

4.  두 경우 중 하나가 정답이라면 정답문자열을, 둘다 false라면 오답문자열을 출력한다.

import java.io.*;
import java.util.*;

public class BOJ_15501_부당한퍼즐 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int[] input = new int[N];
      StringTokenizer st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) input[i] = Integer.parseInt(st.nextToken());
      int[] output = new int[N];
      st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) output[i] = Integer.parseInt(st.nextToken());

      //input, output 같은 숫자 찾아서 거기서부터 양방향 돌리기
      boolean f = true,r = true;
      for(int idx=0;idx<N;idx++){
         if(input[0] != output[idx]) continue;

         //정방향
         for(int i=0;i<N;i++){
            if(input[i]==output[(idx+i)%N]) continue;
            f = false;
            break;
         }

         //역방향
         for(int i=0;i<N;i++){
            if(input[i] == output[(idx+N-i)%N]) continue;
            r = false;
            break;
         }

         if(f||r) System.out.println("good puzzle");
         else System.out.println("bad puzzle");

         return;
      }
   }
}

---

3. 결과

코드를 약간 정리해서 다시 제출했다.