BOJ 16120 PPAP

문제 : BOJ 16120 PPAP

'PPAP'가 나타날 때 마다 'P'로 바꿔준다.

를 효율적으로 구현하지 못해 틀렸다.

시행착오

문자열을 차례로 순회하고,
스택을 두개 써서 하나는 'PPAP'를 만들어 주는 용도로,
다른 하나는 'PPAP'가 되지 못하는 문자들을 넣어주는 용도로 작성했고
정답은 잘 출력 되었으나 시간 초과를 받았다.

문제의 조건에 대해서 길게 생각하지 않고 바로 구현하려는 시도를 한 것이
시간 내에 풀지 못한 원인이라고 생각한다.🥲

풀이

전체 문자열을 순회하며 스택에 넣어주는 것은 맞으나
결국 스택 마지막에 쌓인 'PPAP' 만을 식별해서 'P'로 치환하는 것을 반복해 주면 되는 문제였다.

1. 입력된 문자열을 정방향으로 순회한다.
2. 순회하며 나오는 문자를 스택에 하나씩 쌓는데,
3. 마지막으로 스택에 저장된 문자가 'A' 일 때,
   3-1. 현재 순회중인 문자가 'P'이고, 스택에 쌓인 마지막 세개의 문자가 'P', 'P', 'A' 라면 'PPAP' 완성!
   스택에 쌓인 'P', 'P', 'A'를 제거하고 'P'를 넣어준다.
   3-2. 그렇지 않다면 입력된 문자열은 PPAP 문자열이 아니다.

순회가 종료된 뒤, 스택에 남은 문자가 'P' 하나라면 PPAP 문자열이고,
그렇지 않다면 PPAP 문자열이 아니다.

[ 전체 코드 ]

import sys

def solution():
    ppap = sys.stdin.readline().rstrip()
    stack = []
    for p in ppap:
        if stack and stack[-1] == 'A':
            if p == 'P' and len(stack) >= 3 and stack[-3:] == ['P', 'P', 'A']:
                stack.pop()
                stack.pop()
                stack.pop()
            else:
                print('NP')
                return
        stack.append(p)
    if stack == ['P']:
        print('PPAP')
    else:
        print('NP')

solution()

---