[BOJ] 백준 10266번 시계 사진들 (Java)

#10266 시계 사진들

난이도 : 플레 5

유형 : KMP

10266번: 시계 사진들

▸ 문제

상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바늘들의 위치만 구분 할 수 있습니다.

우리의 상근이는 두 사진의 시계가 같은 시각을 나타낼 수 있는지 궁금해져 각 사진을 서로 다른 각도로 돌려보려고 합니다.

두 사진에 대한 묘사가 주어질 때, 두 사진의 시계가 같은 시각을 나타내는지 결정하세요.

▸ 입력

첫 줄에는 바늘의 수를 나타내는 정수 n(2 ≤ n ≤ 200 000)이 주어진다.

다음 두 줄에는 각각 n개의 정수가 주어지며, 주어지는 정수 ai(0 ≤ ai < 360,000)는 각 사진에서 바늘의 시계 방향 각도를 나타낸다. 이때 바늘의 각도는 특정 순서대로 주어지지는 않는다. 한 줄에는 같은 각도값이 두 번 이상 주어지지 않는다. 즉, 한 시계 안의 모든 각도값은 서로 구분된다.

▸ 출력

두 시계 사진이 같은 시각을 나타내고 있다면 "possible"을 아니면 "impossible"을 출력하시오.

 

문제 풀이  

KMP 유형 문제를 찾아 들어와서 풀었기에 망정이지 모르고 들어왔다면 헤맸을 것 같은 문제이다. 문제를 읽으면 최대 36만*2= 72만이니 환형배열을 사용해서 어떻게 풀면 될 것 같다. 문자열 매칭 KMP 알고리즘과는 잘 매칭이 되지 않는다. KMP까지만 매칭시키면 그 다음 풀이는 수월해진다.

 

KMP로 다음과 같이 풀이하면 된다. '0'과 '1'로만 이루어져 있는 36만개의 문자열을 2배로 확장하여 두 번째로 주어진 문자열과 매칭이 이루어지는지에 대한 여부를 파악하면 된다.

 

문제를 간단하게 하기위해 최대 6개의 문자열이라고 하고 각 clock1 :'010100', clock2: '100010'로 주어졌다하자.

1. clock1을 2배로 확장한다.  clock1 :'010100010100'
2. 확장한 clock1과 clock2를 KMP 매칭 알고리즘을 시킨다.
3. 매칭이 된다면 "possible"을 출력하고 종료한다.
4. clock1 전체 탐색이 끝나도 매칭이 안됐다면 "impossible"을 출력하고 종료한다.

 

0	1	0	1	0	0	0	1	0	1	0	0
			1	0	0	0	1	0

 

풀이 코드 

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

public class Main {
	static final int SIZE = 360_000;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int[] clock1 = new int[SIZE*2];
		int[] clock2 = new int[SIZE];
		StringTokenizer st = new StringTokenizer(br.readLine());
		 for(int i=0; i<n; i++) {
			int num = Integer.parseInt(st.nextToken());
			clock1[num]= 1;
			clock1[SIZE+num]= 1;
		 }
		 st = new StringTokenizer(br.readLine());
		 for(int i=0; i<n; i++) {
			 int num = Integer.parseInt(st.nextToken());
			 clock2[num]= 1;
		 }
		 
		 kmp(clock1, clock2);
		
	}
	static void kmp(int[] c1, int[] c2) {
		int[] table = makeTable(c2);
		int idx=0;
		for(int i=0; i<SIZE*2; i++) {
			while(idx > 0 && c1[i] != c2[idx]) {
				idx = table[idx-1];
			}
			if(c1[i] == c2[idx]) {
				if(idx==SIZE-1) {
					System.out.println("possible");
					return;
				}
				else idx++;
			}
		}
		System.out.println("impossible");
		
	}
	static int[] makeTable(int[] clock) {
		int idx=0;
		int[] table = new int[SIZE];
		for(int i=1; i<SIZE; i++) {
			while(idx>0 && clock[i]!=clock[idx]) {
				idx = table[idx-1];
			}
			if(clock[i] == clock[idx]) {
				table[i] = ++idx;
			}
		}
		return table;
	}
}