[PS] 백준 15501 - 부당한 퍼즐

문제

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

15501번: 부당한 퍼즐

해설

이 문제는 오히려 어렵게 생각하면 한없이 어려워질 수 있는 유형의 문제이다.

 

알고리즘을 어느 정도 공부한 입장에서 처음 문제를 본다면 '뒤집기'와 '좌우로 밀기'를 반복하면서 완전 탐색으로 구현하거나 BFS를 떠올리기 쉽다. 하지만 최대 1,000,000의 n 입력이 주어진다면 메모리 초과 or 시간 초과를 면치 못할 것이다.

 

그렇다면 문제를 다시 한번 읽고 예제 입력 1을 살펴보자.

입력의 둘째 줄에 입력 배열 '1 2 3 4 5'가 주어지고 셋째 줄에 결과 배열 '4 3 2 1 5'가 주어졌다.

 

입력 배열을 위 두 가지 연산만으로 결과 배열을 만들 수 있을지를 보려면 

문제의 1번 조건 '1~n까지의 수열이 한 번씩만 나타난다는데 있다.'에 집중해야 한다.

 

수가 한 번씩만 나오기 때문에 입력 배열의 숫자들의 위치와 결과 배열의 숫자들의 위치는 서로 절대적이다.

 

이 말이 무슨 뜻이냐면 '뒤집기'와 '좌우로 밀기' 연산을 아무리 많이 수행해도 입력 배열 1의 양쪽에는 2와 5가 있고 3의 양쪽에는 2와 4가 있다는 것이다.

 

이제 문제를 해결하기 위해 입력 배열과 결과 배열중 하나를 기준으로 잡아보자.

이 중 어떤 것을 기준으로 잡아도 결과는 동일할 것이다.

 

필자는 입력 배열을 기준으로 하고 0번 인덱스의 값인 1을 결과 배열에서 찾아보겠다.

3번 인덱스에서 1이 발견되었고 그 좌우를 살펴보면 된다.

그중 입력 배열의 1번 인덱스의 값과 일치하는 방향으로 살펴보면서 길이 n까지 동일하다면

good puzzle이고 그렇지 않다면 bad puzzle이 될 것이다.

 

이를 구현한 코드를 살펴보자.

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

/**
 * @memory 	230244KB / 256MB
 * @time   		608ms / 2초
 */
public class BOJ_S3_15501_부당한퍼즐 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
		StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
		int[] arr = new int[n], brr = new int[n];
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(st1.nextToken());
			brr[i] = Integer.parseInt(st2.nextToken());
		}
		if (n == 1) {
			System.out.print("good puzzle");
			return;
		}
		
		boolean a = true, b = true;
		for (int i = 0; i < n; ++i) {
			if (arr[0] == brr[i]) {
				int j = i == n-1 ? 0 : i+1;
				if (arr[1] == brr[j]) {
					for (int k = 2; k < n; ++k) {
						j = j == n-1 ? 0 : j+1;
						if (arr[k] != brr[j]) {
							a = false;
							break;
						}
					}
				} else a = false;
				j = i == 0 ? n-1 : i-1;
				if (arr[1] == brr[j]) {
					for (int k = 2; k < n; ++k) {
						j = j == 0 ? n-1 : j-1;
						if (arr[k] != brr[j]) {
							b = false;
							break;
						}
					}
				} else b = false;
				if (a || b) System.out.print("good puzzle");
				else System.out.print("bad puzzle");
				return;
			}
		}
		System.out.print("bad puzzle");
	}
}

 

어떤 문제를 만나느냐에 따라 특정한 알고리즘으로만 해결되는 문제가 있고 그렇지 않은 문제가 있다. 이 문제는 위 해설을 읽어보았듯이 특별한 알고리즘이 사용되지는 않았다.

 

하지만 오히려 알고리즘 기법을 사용하면 해결할 수 없었을 것이다. 만약 이 문제의 해결방법을 떠올리는데 오랜 시간이 걸렸다면 앞으로 많은 문제를 보고 처음 보는 유형에 익숙해지는 것이 가장 좋은 해결책이 아닐까 하는 생각이 든다.