11월 8일 - 시계 사진들[BOJ/10266]

두 개의 시계 사진을 서로 회전시켜 같은 시각을 나타내는지 확인하는 문제를 풀었다. 각 시계는 여러 바늘을 가지고 있고, 각 바늘은 시계 방향으로 특정 각도 위치에 있으며, 두 시계의 바늘 배치가 서로 다를 수 있다. KMP 알고리즘을 활용해 두 시계의 바늘 배치가 일치할 수 있는지를 판별했다.

문제 접근 방법

1. KMP 알고리즘을 통한 회전 매칭:

• 두 시계가 동일한 시각을 나타내려면 하나의 시계를 여러 방향으로 회전시켰을 때 다른 시계의 배치와 일치해야 한다.
• 이를 위해 두 번째 시계를 첫 번째 시계의 두 배 길이의 배열로 확장하고, 두 배열이 일치하는 부분이 있는지 KMP 알고리즘으로 찾았다.

2. 바늘의 각도 차이를 기반으로 한 상태 저장:

• 각 시계의 바늘 위치를 나타내기 위해 각도를 boolean 배열로 저장했다.
• 첫 번째 시계는 360,000을 기준으로 배열을 두 배로 늘려서, 한 바퀴를 넘어서도 회전하면서 비교할 수 있게 했다.

3. KMP 알고리즘 활용:

• KMP 알고리즘은 문자열 검색에서 주로 쓰이지만, 이 문제에서는 회전 매칭을 위해 사용했다.
• 첫 번째 시계를 두 배 길이로 만들고 두 번째 시계와 비교해 패턴이 일치하는 구간이 있는지 찾는다.

코드

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

public class Main {
    static final int MAX = 360000;

    // KMP 알고리즘의 pi 배열을 구하는 메서드
    public static int[] getPi(boolean[] pattern) {
        int[] pi = new int[pattern.length];
        int j = 0;

        for (int i = 1; i < pattern.length; i++) {
            while (j > 0 && pattern[i] != pattern[j]) {
                j = pi[j - 1];
            }
            if (pattern[i] == pattern[j]) {
                pi[i] = ++j;
            }
        }
        return pi;
    }

    // KMP 알고리즘을 이용한 패턴 매칭
    public static boolean kmp(boolean[] text, boolean[] pattern) {
        int[] pi = getPi(pattern);
        int j = 0;

        for (int i = 0; i < text.length; i++) {
            while (j > 0 && text[i] != pattern[j]) {
                j = pi[j - 1];
            }
            if (text[i] == pattern[j]) {
                if (j == pattern.length - 1) {
                    return true; // 매칭 성공
                } else {
                    j++;
                }
            }
        }
        return false; // 매칭 실패
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine().trim());

        // 첫 번째 시계의 각도를 저장할 배열
        boolean[] clock1 = new boolean[MAX * 2];
        boolean[] clock2 = new boolean[MAX];

        // 첫 번째 시계 각도 입력 및 표시
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int angle = Integer.parseInt(st.nextToken());
            clock1[angle] = true;
            clock1[MAX + angle] = true; // 시계 방향으로 회전 가능성 추가
        }

        // 두 번째 시계 각도 입력 및 표시
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int angle = Integer.parseInt(st.nextToken());
            clock2[angle] = true;
        }

        // KMP 알고리즘을 사용하여 같은 시각인지 확인
        System.out.println(kmp(clock1, clock2) ? "possible" : "impossible");
    }
}

코드 설명

1. KMP 알고리즘을 위한 pi 배열 구하기:

public static int[] getPi(boolean[] pattern) {
    int[] pi = new int[pattern.length];
    int j = 0;

    for (int i = 1; i < pattern.length; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            pi[i] = ++j;
        }
    }
    return pi;
}

• getPi 함수는 KMP 알고리즘에서 접두사와 접미사 일치 정보를 저장하는 pi 배열을 구하는 함수다.
• pattern 배열을 순회하며 접두사와 접미사가 일치하는 부분의 길이를 pi 배열에 저장한다.
• pi 배열은 반복적인 패턴을 빠르게 찾기 위해 사용된다.

2. KMP 알고리즘을 이용한 패턴 매칭:

public static boolean kmp(boolean[] text, boolean[] pattern) {
    int[] pi = getPi(pattern);
    int j = 0;

    for (int i = 0; i < text.length; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            if (j == pattern.length - 1) {
                return true; // 매칭 성공
            } else {
                j++;
            }
        }
    }
    return false; // 매칭 실패
}

• kmp 함수는 text 배열에서 pattern 배열을 찾는 KMP 알고리즘이다.
• text 배열을 순회하며 pattern과 일치하는 부분이 있는지 검사하고, 일치하는 부분이 있으면 true를 반환하여 시계가 같은 시각을 나타낼 수 있음을 나타낸다.

3. 입력 및 각도 배열 설정:

int n = Integer.parseInt(br.readLine().trim());

boolean[] clock1 = new boolean[MAX * 2];
boolean[] clock2 = new boolean[MAX];

StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
    int angle = Integer.parseInt(st.nextToken());
    clock1[angle] = true;
    clock1[MAX + angle] = true; // 시계 방향으로 회전 가능성 추가
}

st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
    int angle = Integer.parseInt(st.nextToken());
    clock2[angle] = true;
}

• 첫 번째 시계의 각도를 clock1 배열에 저장하고, 시계 방향으로 회전하는 것을 표현하기 위해 두 배 길이의 배열로 확장했다.
• 두 번째 시계의 각도는 clock2 배열에 저장한다.

4. KMP를 통한 패턴 매칭 결과 출력:

System.out.println(kmp(clock1, clock2) ? "possible" : "impossible");

• kmp 함수를 통해 clock1 배열에서 clock2 배열을 찾고, 결과에 따라 possible 또는 impossible을 출력한다.

So....

KMP 알고리즘을 통해 두 시계의 바늘 배치가 일치하는지 효율적으로 확인할 수 있었다. 두 시계를 직접 회전시키며 비교하는 대신, 첫 번째 시계를 두 배 길이로 확장하여 회전하는 효과를 시뮬레이션하고, KMP 알고리즘으로 이를 패턴 매칭으로 처리한 것이 핵심이다.