[Problem Solving] BOJ 16120: PPAP

문제 출처: https://www.acmicpc.net/problem/16120

 

문자열에 있는 P를 PPAP로 바꿀 수 있다고 할 때 이 과정을 반복해서 만들어진 문자열을 PPAP문자열이라고 한다. 주어진 문자열이 PPAP 문자열인지 판단하는 문제이다.

이 문제는 스택을 사용하면 O(len(word))에 풀 수 있다.

 

문자열 왼쪽에서 오른쪽 순서로 stack에 추가한다.

stack의 길이가 4개 이상이 되면 가장 최근에 들어간 4개의 문자열이 PPAP인지 확인하고 그렇다면 4개를 빼고 P를 넣는다.

주어진 문자열이 PPAP 문자열이었다면 스택에는 P 하나만 남게 된다. 그렇다면 PPAP를 출력하고 그렇지 않다면 NP를 출력한다.

 

import sys
read = sys.stdin.readline

word = read().rstrip()
PPAP = "PPAP"
stack = []
for i in range(len(word)):
    stack.append(word[i])
    if len(stack) >= 4:
        four_of_top = stack[-4] + stack[-3] + stack[-2] + stack[-1]
        if four_of_top == PPAP:
            for _ in range(4):
                stack.pop()
            stack.append("P")

if len(stack) == 1 and stack[0] == "P":
    print("PPAP")
else:
    print("NP")