11월 26일 - Slot Machines[BOJ/14959]

문제 해결 코드

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

public class Main {

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

        // 입력
        int n = Integer.parseInt(br.readLine());
        int[] sequence = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            sequence[i] = Integer.parseInt(st.nextToken());
        }

        // 순서를 뒤집음
        int[] reversedSequence = new int[n];
        for (int i = 0; i < n; i++) {
            reversedSequence[i] = sequence[n - 1 - i];
        }

        // 실패 함수 계산
        int[] pi = computePi(reversedSequence);

        // 최소 k와 p 계산
        int k = 0, p = 0, total = Integer.MAX_VALUE;
        for (int i = 0; i < pi.length; i++) {
            int currentK = pi.length - (i + 1);
            int currentP = (i + 1) - pi[i];
            if (currentK + currentP < total) {
                total = currentK + currentP;
                k = currentK;
                p = currentP;
            }
        }

        // 결과 출력
        System.out.println(k + " " + p);
    }

    private static int[] computePi(int[] pattern) {
        int n = pattern.length;
        int[] pi = new int[n];
        int j = 0;

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

        return pi;
    }
}

코드 설명

1. 입력 처리

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

• 길이 n과 시퀀스 데이터를 입력받아 배열 sequence에 저장한다.

2. 시퀀스 뒤집기

int[] reversedSequence = new int[n];
for (int i = 0; i < n; i++) {
    reversedSequence[i] = sequence[n - 1 - i];
}

• KMP 알고리즘을 이용하기 위해 시퀀스를 뒤집는다. 패턴 매칭에서 뒤에서부터 주기를 찾아야 하기 때문이다.

3. KMP의 실패 함수 계산

private static int[] computePi(int[] pattern) {
    int n = pattern.length;
    int[] pi = new int[n];
    int j = 0;

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

    return pi;
}

• KMP의 실패 함수(pi)를 계산한다.
• pi[i]는 문자열에서 i번째 위치까지의 접미사와 접두사의 최대 일치 길이를 나타낸다.

4. 최소 k와 p 계산

int k = 0, p = 0, total = Integer.MAX_VALUE;
for (int i = 0; i < pi.length; i++) {
    int currentK = pi.length - (i + 1);
    int currentP = (i + 1) - pi[i];
    if (currentK + currentP < total) {
        total = currentK + currentP;
        k = currentK;
        p = currentP;
    }
}

• k는 비주기적으로 생성된 패턴의 길이를 나타내고, p는 반복되는 주기의 길이이다.
• k + p가 최소인 경우를 찾는다. 동률인 경우 p가 작은 값을 선택한다.

So...

이 문제는 KMP 알고리즘의 실패 함수를 활용해 주기를 탐지하는 방법을 요구한다. 입력 데이터를 뒤집어서 처리해야 했기 때문에 KMP의 패턴 매칭을 변형하여 사용했다. 처음에는 k와 p의 정의와 관계를 파악하는 데 시간이 걸렸지만, KMP의 원리를 응용하여 효율적으로 해결할 수 있었다. 주기를 탐지하고 최적의 패턴을 찾는 문제에서 KMP는 강력한 도구임을 다시 한번 느꼈다.