[Platinum IV] 시계 사진들 - 10266

문제 링크

성능 요약

메모리: 50832 KB, 시간: 532 ms

분류

KMP, 문자열

제출 일자

2024년 8월 28일 16:23:56

문제 설명

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

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

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

입력

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

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

출력

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

문제 풀이

KMP알고리즘 문제.
시계각도가 0~359999까지 있고 회전 가능하므로 회전 고려하여 길이 720000텍스트 clock1과 길이 360000의 패턴 clock2를 비교한다고 생각.
boolean배열로 720000짜리 clock1에 회전 고려한 텍스트 표시, 360000짜리 clock2에 패턴 표시. KMP알고리즘 적용.

코드

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

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static int n;
	static boolean[] clock1, clock2;
	static int[] pi;
	public static void main(String[] args) throws IOException {
//		br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		n = Integer.parseInt(br.readLine());
		clock1 = new boolean[720000];
		clock2 = new boolean[360000];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			int n = Integer.parseInt(st.nextToken());
			clock1[n] = true;
			clock1[n + 360000] = true;
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			int n = Integer.parseInt(st.nextToken());
			clock2[n] = true;
		}
		pi = getPi();
		
		System.out.println(KMP() ? "possible" : "impossible");
		
	}
	private static boolean KMP() {
		
		int j=0;
		for(int i=0; i<720000; i++) {
			 while(j>0 && clock1[i] != clock2[j]) {
				 j = pi[j-1];
			 }
			 if(clock1[i] == clock2[j]) {
				 if(j==359999) {
//					 j=pi[j];
					 return true;
				 }
				 else j++;
			 }
		 }
		return false;		
	}
	private static int[] getPi() {
		 int[] pi = new int[360000];
		 int j=0;
		 for(int i=1; i<360000; i++) {
			 while(j>0 && clock2[i] != clock2[j]) {
				 j = pi[j-1];
			 }
			 if(clock2[i] == clock2[j]) pi[i] = ++j;
		 }
		 return pi;
	}
}