[baekjoon] 백준 16120번(파이썬): PPAP

문제

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인지 확인하여 맞으면 바로 PPAP를 출력한다.

- 틀리다면 문자열을 반복하여 문자를 확인한다.

- 스택을 이용하여 문자를 추가하고 스택에 뒤에서 4번째까지 문자가 ["P", "P", "A", "P"] 일 경우 첫 번째 P만을 남기고 모두 팝 한다.

- 스택 리스트에 ["P", "\n"]가 있으면 모든 PPAP를 P로 바꿔준 것으로 PPAP를 출력

- 그게 아니라면 PPAP가 아니므로 NP를 출력

코드

import sys

c = sys.stdin.readline()
stack = []
# 주어진 문자열이 P이거나 PPAP이면 PPAP 출력
if c == "P" or c == "PPAP":
    print("PPAP")
else:
    # 문자열을 반복하여 문자를 확인
    for i in c:
        # 문자를 스택에 추가
        stack.append(i)
        
        # 스택 리스트 뒤에서 4번째까지 문자가 ["P", "P", "A", "P"]일 경우 
        # 첫 번째 P만 남기고 팝한다.
        if stack[-4:] == ["P", "P", "A", "P"]:
            stack.pop()
            stack.pop()
            stack.pop()
    # 스택 리스트에 ["P", "\n"]가 있으면 모든 PPAP를 P로 바꿔준 것으로 PPAP 출력 
    if stack == ["P", "\n"]:
        print("PPAP")
        
    # 그게 아니라면 PPAP가 아니므로 NP 출력
    else:
        print("NP")

github

junjange/CodingTest