[BOJ 16120, Python 3] PPAP

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

16120번: PPAP

 

풀이

문제를 잘 읽어보면 알파벳 P에서부터 시작하는 것이라서 PP, PPPP이런 것은 PPAP 문자열이 될 수 없습니다.

그리고 문제에서는 P를 PPAP로 변경하는 것이지만, 이걸 거꾸로 뒤집으면 PPAP를 P로 만들 수 있습니다.

따라서 스택에 문자열을 하나씩 저장하다가 마지막 4글자가 PPAP이면 원소를 4개를 빼고 P를 넣어주면 됩니다.

 

→ 방향으로 문자열을 저장해 나가는 것이 틀릴 수도 있는 것이 아니냐 생각하실 수도 있는데, P에서부터 시작하여 P를 PPAP로 변경해나갔으니 아무렇게나 PPAP를 P로 줄여도 결국엔 PPAP 문자열이라면 P로 만들 수 있기 때문에 상관이 없습니다. 그래서 편하게 코드를 짤 수 있도록 → 방향으로 문자열을 저장해나가는 것입니다.

 

 

코드

s = input()
q = []
for i in range(len(s)):
    q.append(s[i])
    while len(q) >= 4 and q[len(q)-4:] == ['P', 'P', 'A', 'P']:
        for j in range(4): q.pop()
        q.append('P')
print(['NP','PPAP'][q == ['P']])