[골드 4] 백준 16120 - PPAP (파이썬)

https://www.acmicpc.net/problem/16120

풀이

문자열이 PPAP 규칙에 따라서 만들어졌는지 판별하는 문제이다.

• 기본적인 규칙은 PPAP는 P로 줄일 수 있다.
• PPPAP는 PPAP + P → PP가 되지 않으므로 올바른 형태가 아니다.
• 줄이고 줄이다가 마지막에 P 하나만 남으면 PPAP 문자열이라고 한다.

S = input()
stack = []

입력 문자열 S를 한글자씩 처리할 것이며, 처리 중간 결과를 저장하기 위해서 스택을 사용한다.

for i in range(len(S)) :
    stack.append(S[i])

입력 문자열의 각 문자를 stack에 순차적으로 쌓는다.

while len(stack) >= 4 and "".join(stack[-4:]) == "PPAP" :
    for _ in range(3) :
        stack.pop(-1)

stack의 가장 마지막 4개의 문자가 PPAP일 경우 이를 P로 축약할 수 있다.

즉, 뒤에서 3개 PPA를 제거하고 마지막 남은 P만 남긴다.

이 과정을 반복함으로써 중첩된 PPAP도 처리할 수 있다.

예제에서 PPPAPPPAP라고 하면 다음과 같이 처리된다.

단계 현재 문자 스택 상태 줄이기 발생 줄인 후 스택

1	P	['P']	❌	-
2	P	['P', 'P']	❌	-
3	P	['P', 'P', 'P']	❌	-
4	A	['P', 'P', 'P', 'A']	❌	-
5	P	['P', 'P', 'P', 'A', 'P']	✅ "PPAP"	['P', 'P']
6	P	['P', 'P', 'P']	❌	-
7	P	['P', 'P', 'P', 'P']	❌	-
8	A	['P', 'P', 'P', 'P', 'A']	❌	-
9	P	['P', 'P', 'P', 'P', 'A', 'P']	✅ "PPAP"	['P', 'P', 'P']

코드

# 백준 16120 - PPAP
# 분류 : 스택

S = input()

stack = []
for i in range(len(S)) :
    stack.append(S[i])

    while len(stack) >= 4 and "".join(stack[-4:]) == "PPAP" :
        for _ in range(3) :
            stack.pop(-1)

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