[Stack] 백준 - PPAP 16120번

문제 링크 - 백준 문제 PPAP

처음 풀이법

문자열의 4부분에 'PPAP'가 있다면 그것을 'P'로 바꾸어주었다.

for i in range(0,len(word)):
    stack += word[i]

    if len(stack) >= 4:
        if stack[-4:] == 'PPAP':
            stack = stack[:-4] + "P"

즉 string += string의 형태로 코드를 작성할 경우 시간복잡도가 O(n^2)이 시간초과 오류가 계속 떴었다.

해답

따라서 입력받은 문자열을 stack이라는 리스트에 넣어서 만약 마지막 4개의 단어가 ['P','P','A','P']일 경우 나머지 3개의 단어를 pop하여 'P'만 남게 하였다.

#PPAP
import sys
input = sys.stdin.readline

word = input().strip()

#시간복잡도를 줄이기 위해 문자열을 리스트로 하나씩 입력받는다. 
stack = []

for i in range(0,len(word)):
    stack.append(word[i])

    #만약 마지막 4단어가 PPAP일 경우 맨 앞 P를 제외한 나머지 단어들을 제외(pop)시킨다. 
    if stack[-4:] == ['P','P','A','P']:
        stack.pop()
        stack.pop()
        stack.pop()

if stack == ['P'] or stack == ['P','P','A','P']:
    print('PPAP')

else:
    print('NP')