[백준] 16120번 - PPAP

📩 출처

문제

bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다.

PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다.

• P는 PPAP 문자열이다.
• PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.

예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다.

문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라.

입력

첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.

출력

첫 번째 줄에 주어진 문자열이 PPAP 문자열이면 PPAP를, 아닌 경우 NP를 출력한다.

👉 생각

• 이 문제는 구현하는 것보다 문제를 이해하는게 더 어려웠던 것 같다.. 결과적으로는 주어지는 문자열에서 'PPAP'가 있다면 'P'로 계속 치환한 후에 제일 마지막에 남는 문자가 'P'라면 'PPAP'를 출력하고 그렇지 않으면, 'NP'를 출력하면 된다.
• 스택 자료구조를 사용하여 'P'일때 stack의 마지막 3개가 'PAP'라면 stack에서 제거해주고 'P'를 넣어준다.
• 초기값으로 x를 넣어준 이유는 인덱스 에러가 나지 않게하기 위함이다!

word = input()
stack = ['x'] * 3
for i in range(len(word)):
    if word[i] == 'P':
        if stack[-1] == 'A' and stack[-2] == 'P' and stack[-3] == 'P':
            stack.pop(-1)
            stack.pop(-1)
            stack.pop(-1)
    stack.append(word[i])

if ''.join(stack[3:]) == 'P':
    print('PPAP')
else:
    print('NP')