(BOJ11585 속타는 저녁 메뉴

• tags : (algorithm

  No matching post could be found

• 문제 링크 : https://www.acmicpc.net/problem/11585
• 풀이 링크
  • Python

• 문자열을 1회 회전하며 문자열 패턴을 찾는 문제
• 문자열을 1회 회전하는것은 같은 문자열을 2번 이어 붙여서 탐색하는 것으로 해결할 수 있다.
• 탐색하는 문자열은 처음 주어진 문자열의 특정 회전 중 하나이므로, 최종 탐색 위치만 잘 고민하면 된다.

def get_lps(N: int, target: list):
    lps = [0] * N
    idx = 1
    len_idx = 0
    while idx < N:
        if target[idx] == target[len_idx]:
            len_idx += 1
            lps[idx] = len_idx
            idx += 1
        else:
            if len_idx:
                len_idx = lps[len_idx - 1]
            else:
                idx += 1
    return lps

• 빠른 패턴 매칭을 위한 lps를 구하는 함수
• 각 인덱스마다 같은 접두어와 접미어를 찾아 저장한다.

def kmp(N: int, roulette: list, target: list, lps: list):
    count = 0
    idx = target_idx = 0
    while idx < N * 2 - 1:
        if roulette[idx] == target[target_idx]:
            idx += 1
            target_idx += 1
        else:
            if target_idx:
                target_idx = lps[target_idx - 1]
            else:
                idx += 1
        if target_idx == N:
            count += 1
            target_idx = lps[target_idx - 1]
    return count

• KMP 연산 함수
• while문을 실행할 때, idx < N * 2라고 하면, 1개를 더 찾을수도 있으므로 범위를 찰 지정해야한다.
• 처음 if-else 문에서는 KMP 알고리즘을 적용했다.
  • 만약 탐색하는 문자열, 목표 문자열의 각 위치의 값이 같다면, 인덱스를 증가
  • 만약 다르다면 목표 문자열에 대해 이미 구해놓은 lps를 활용하여 탐색할 위치의 인덱스를 찾는다.
• 탐색 문자열을 찾았다면, 해당 인덱스를 반환하는 대신, 더 탐색하기 위해 목표 문자열의 탐색에 대한 인덱스만 수정한다.

N = int(input())
roulette = list(input().strip().split())
target = list(input().strip().split())
if roulette == roulette[0] * N:
    print("1/1")
    exit()
lps = get_lps(N, target)
count = kmp(N, roulette + roulette, target, lps)
g = gcd(N, count)
print(f"{count // g}/{N // g}")

• 최종 코드는 다음과 같다.