[Algorithm] 10266 - 시계 사진들 (JAVA)

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

10266번: 시계 사진들

알고리즘 

처음엔 정렬해서 KMP 알고리즘으로 비교하려고 했다. 하지만 바늘의 수가 20만까지 주어지기 때문에 시간초과가 난다. 다른 블로그를 참조해서 배열에 담아 비교하는 방법을 터득했다. 주어지는 정수는 0부터 36만까지이므로 arr을 텍스트로 (36*2인 72만 크기)로 만들고 arr2를 찾을 패턴인 (36만)으로 생성해서 입력받는 값을 배열에 담는다.

예시를 봐보자. 문제의 예제 입력 1번을 보면 arr1은 (1,2,3,4,5,6), arr는 (7,6,5,4,3,1) 이 주어진다.  단, 텍스트는 arr,arr2를 이어 붙인 배열로 판별하기 위해서 배열에 담을 때 기준 크기인 36만차이로 더 담아야한다. 설명을 위해 예시는 36만이 아닌 6으로 들겠다.

arr에 배열을 담을 때 1이면 arr[1]과 1+6인 arr[7]에 1을 담는다. 이와 같은 방법으로 arr을 텍스트로 담고 arr2를 KMP 알고리즘으로 실패함수 인덱스를 비교해서 일치하면 possible, 불일치하면 impossible을 출력하면 된다.

코드 

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

public class Main {
	// 기준인 36만을 상수로 정의
    static final int NUM = 360_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        // 텍스트인 arr을 72만, arr2를 36만으로 초기화
        int[] arr = new int[NUM * 2];
        int[] arr2 = new int[NUM];
        int num;
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<n; i++) {
            num = Integer.parseInt(st.nextToken());
            arr[num] = 1;
            // arr1 + arr2를 합친 크기로 비교해야하기 때문에 입력받은 값을 한번 더 넣어준다
            arr[num+NUM] = 1;
        }
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<n; i++) {
            num = Integer.parseInt(st.nextToken());
            arr2[num] = 1;
        }
        chkIsSame(arr, arr2);
    }
    private static void chkIsSame(int[] arr, int[] arr2) {
        // arr2의 실패함수를 만들어서 비교
        int[] pi = makePi(arr2);
        int j = 0;
        for (int i = 1; i < arr.length; i++) {
        	// 직전 부분 문자열이 존재하지만 현재 비교 값이 다른 경우
            while (j > 0 && arr[i] != arr2[j]) {
                j = pi[j-1];
            }
            // 현재 비교 문자열이 같은 경우
            if (arr[i] == arr2[j]) {
            	// j 가 NUM-1 까지 도달하면 패턴과 텍스트가 일치
                if (j == NUM-1) {
                    System.out.println("possible");
                    return;
                }
                else ++j;
            }
        }
        System.out.println("impossible");
    }
    // 실패함수 생성 메서드
    private static int[] makePi(int[] array) {
        int[] pi = new int[NUM];
        int j = 0;
        for (int i = 1; i < NUM; i++) {
            while (j > 0 && array[i] != array[j]) {
                j = pi[j-1];
            }
            if (array[i] == array[j]) pi[i] = ++j;
        }
        return pi;
    }
}