[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 16120번 _ PPAP

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

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를 출력한다.

 

[아이디어]

1) 처음에 문자열 길이가 최대 100만임을 간과하고 그냥 replace를 사용하면 된다고 생각했는데, 시간 초과가 났다.

2) 괄호 쌍 제거와 유사하게 스택을 활용해 PPAP가 완성 될때마다 스택의 일부를 비우는 방법을 사용했다.

 

# 시간 초과
import re
s=input()
p = re.compile("PPAP")
while "PPAP" in s and s!="PPAP":
    s = re.sub(p,"P",s)
print(s if s=="PPAP" else "NP")

s = []
for x in input():
    if s[-3:]==["P","P","A"] and x=="P":
        s[-2:] = []
    else:
        s.append(x)
print("PPAP" if s==["P"] else "NP")

아래가 통과 코드. PPAP가 될 때마다 P 하나를 남기고 두 개를 비우면 된다.