[Python] 백준 11585번: 속타는 저녁 메뉴

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

11585번: 속타는 저녁 메뉴

 

import sys
input = sys.stdin.readline


def get_pi(keyword):
    keyword_length = len(keyword)
    pi = [0]*keyword_length

    j = 0
    for i in range(1, keyword_length):
        while keyword[i] != keyword[j] and j > 0:
            j = pi[j-1]

        if keyword[i] == keyword[j]:
            j += 1
            pi[i] = j

    return pi


def find_keyword(string, keyword):
    keyword_count = 0
    string_length = len(string)
    keyword_lenght = len(keyword)

    i, j = 0, 0
    while i < string_length:
        if string[i] == keyword[j]:
            i += 1
            j += 1
        else:
            if j == 0:
                i += 1
            else:
                j = pi[j-1]

        if j == keyword_lenght:
            keyword_count += 1
            j = pi[j-1]

    return keyword_count


if __name__ == '__main__':
    N = int(input())
    target = list(map(str, input().split()))
    roulette = list(map(str, input().split()))
    roulette += roulette[:-1]

    # KMP를 통해 target의 갯수를 가져옴
    pi = get_pi(target)
    target_count = find_keyword(roulette, target)

    # 최대공약수를 찾은 뒤, 여기에 맞추어 출력함
    for i in range(target_count, 0, -1):
        if target_count % i == 0 and N % i == 0:
            print("{0}/{1}".format(target_count//i, N//i))
            break

 

이 글은 KMP 알고리즘을 알고 있다는 전제 하에 작성하였다. KMP 알고리즘에 대한 상세한 설명은 아래 글에 작성되어 있다.

 

https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-1893%EB%B2%88-%EC%8B%9C%EC%A0%80-%EC%95%94%ED%98%B8

[Python] 백준 1893번: 시저 암호

 

우선 룰렛을 2배로 이어붙인 뒤 거기서 마지막 문자를 자른 상태로 만들어준다. ABCDE를 ABCDEABCD로 만들어주겠다는 뜻이다. 여기에 KMP를 이용하여 고기를 선택하게 되는 문자를 검색하고 그 갯수를 가져온다.(target_count)

마지막으로 이것을 형식에 맞게 출력해주면 된다. 최대공약수를 찾고 그것으로 나누어 출력해주었다.

 

KMP만 알면 바로 풀 수 있는 문제이다.