[백준 16120번] PPAP (Python/파이썬)

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

16120번: PPAP

C++ 연습을 위해 C++로 하려고 했는데 문자열 = 파이썬이라는 명언을 기억하고 파이썬으로 풀었다.

맨처음에는 최대로 문자열을 줄였을때 P가되면 PPAP문자열이다.라고 생각하고 코드를 짰더니 O(n^2)이 나와서 다시 지우고 다시했다.

O(n)으로 즉 한번의 탐색만으로 문자열을 최대로 줄이기 위해 스택을 이용하였다.예를들어 PPPAPAP가 있다고 하면하나씩 스택에 넣다가 마지막 4개의 문자가 'P', 'P', 'A', 'P'이면 'P'로 만들어야 하므로 3번을 pop해준다.이렇게 하면 연속적으로 줄여진 상태의 문자열에서도 바로바로 PPAP문자열을 확인할 수 있다.코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
ppap = []
s = input().rstrip()
ans = 'NP'
for i in s:
  ppap.append(i)
  if len(ppap) >= 4 and ppap[-4:] == ['P','P','A','P']:
    for _ in range(3):
      ppap.pop()
if len(ppap) == 1 and ppap[0] == 'P':
  ans = 'PPAP'
print(ans)

 

 

 

 

그리디는 확실히 골드 5까지는 바로바로 풀리는데 골드 4~3부터는 생각이 좀 필요한거 같다.