알고스팟 PPAP (PPAP) 문제 파이썬으로 풀기

https://algospot.com/judge/problem/read/PPAP

algospot.com :: PPAP

사진으로 하기엔 너무 길어서 링크로 대체한다.

문제 자체는 "pen-pineapple-apple-pen/"이라는 문구가 계속해서 이어진 문자열에서 입력 받은 문자열이 몇 번이나 있는지 출력하는 것이다.

 

매우 쉽게 풀릴거같은 문제였지만, 꽤 많이 고생을 했다. 그 이유로는 두가지가 있다.

첫번째 이유는 확실치는 않지만, 겹치는 경우도 생각을 해야한다는 것이다. 앞서 말했듯, "pen-pineapple-apple-pen/"이 24자가 반복되는 문자열에서 입력받은 문자열이 몇 번 나타나는지 알아보는게 문제가 원하는 것이다.

예를 들어, "pen-pineapple-apple-pen/" 이 5번 반복되는 문자열이 있다고 하자. 그리고 그 문자열에서 "pen-pineapple-apple-pen/pen"을 찾고 싶다고 가정하자. 파이썬에서 문자열의 갯수를 찾을때, 가장 간편하게 찾는 방법은 count를 이용하는 것이다. 

pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/

여기서 count 함수를 이용해 "pen-pineapple-apple-pen/pen"을 찾으면, 

pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/

이렇게 5번이 나온다.

이 방법 외에도, split함수를 이용해 문자열을 나누고, 그 수에서 1을 뺀 수를 구하는 방법도 있는데, 이것도 count 함수를 쓸 때와 동일한 결과가 나온다.

하지만 문제에서는 겹치는 경우를 용인하는 거 같았다. 즉,

pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/pen-pineapple-apple-pen/

주황색 배경과 볼드체를 포함해 5번이 아니라, 9번이 되는 것이다.

비록 확증은 없지만, count나 split을 이용해 (알고리즘 이용 안함)구현했을때 오답이 계속해서 뜬걸 보니 의심이 든다.

 

두번째 이유는 주어진 시간이 짧다는 것이다. 이 문제의 시간 제한은 1000ms이다. 문자열을 다루는 문제에서 파이썬을 이용한다면 1000은 좀 짧다고 생각한다. 개인적으로 이렇게 생각하는 것 말고도, 이 시간제한 때문에 맞은 답안을 시간초과라고 판정을 받기도 했다.

정확히 말하자면, 알고리즘을 이용해 잘 구현을 했다고 한 답안이 시간초과가 떳는데, 혹시 몰라 재채점을 눌러보니 996ms로 정답이 떳다. 파이썬이 정말 느리다는걸 다시끔 깨닫게 되었다.

 

아무튼 문제로 다시 돌아가서, 삽질을 꽤 많이 하다가 어떻게 문제를 풀지 찾아보았는데, kmp 알고리즘이란 것을 이용해서 문제를 풀었다는 것을 발견했다.

kmp알고리즘이란 간단히 말해, 문자열의 접두사들과 접미사들을 비교해, 문자열을 찾는데 걸리는 시간을 단축하는 알고리즘이다. 

https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

자세한 내용은 이 링크에 잘 나와있으니 참고하길 바란다. (나도 아직 완전히 이 알고리즘을 이해하지는 못하고 가져다 쓰기만 하였다.)

 

그래서 파이썬 코드로 구현한 것은 밑과 같다.

#ppap
# kmp 알고리즘을 이용하였다.
def getpi(p):
    m = len(p)
    j = 0
    pi = [0 for o in range(m)]
    for i in range(1, m):
        while p[i] != p[j]:
            if j == 0:
                pi[i] = j
                break
            j = pi[j-1]
        if p[i] == p[j]:
            j += 1
            pi[i] = j
    return pi
 
 
def kmp(s, p):
    ans = []
    pi = getpi(p)
    n = len(s)
    m = len(p)
    j = 0
    for i in range(n):
        while s[i] != p[j]:
            if j == 0:
                break
            j = pi[j-1]
        if s[i] == p[j]:
            j += 1
            if j == m:
                ans.append(i-m+2)
                j = pi[j-1]
    return ans
 
 
ppapstring = "pen-pineapple-apple-pen/"
l, r, p = map(str, input().split())
l = int(l)
r = int(r)
ppap = ppapstring*42000  # 문제의 기준인 백만보다 조금 많이 만들음
nppap = ppap[l-1:r]  # 실제로 필요한 문자열
result = kmp(nppap, p)
print(len(result))
 

4ms만 더 길었다면 또 시간초과가 떳을것이다. 어우..

 

느낀점:

1. 파이썬은 느리다! 하여간 느리다!

2. 이 문제를 한달쯤 전 시도했는데 실패해서 벼르고 있었는데, 이번에 정답이 나와서 마음이 편해졌다. 

3. kmp 알고리즘에 대해 좀 더 읽어봐야겠다. 내가 건 링크도 중간까지는 이해가 잘 되었는데, 갑자기 이해가 안되게 되어서 당황했다. 다른 링크들도 읽어봤지만 마찬가지였다. 손으로 써가면서 보면 나아지려나?