[PYTHON] 백준 16120 - PPAP

성능 요약

메모리: 188052 KB, 시간: 268 ms

분류

자료 구조, 그리디 알고리즘, 스택, 문자열

문제 설명

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를 넣는다.
• P는 올바른 출력이다.
• 한번에 4개를 뺄건데, 그 과정을 어떻게 진행하는게 가장 효율적일까?

---

TROUBLE SHOOTING

• 일단 이 문제를 풀기위해 진행했던 실패코드들을 올리며 트러블 슈팅을 진행하겠다.

• “PP”, “PA”, “AP”, “AA” 로 나누면 좀더 쉽고 간단하게 풀이가 가능할거라 생각헀다.

  if n_list[i] == "PP":
      stack.append(n_list[i])
  elif n_list[i] == "PA":
  
  elif n_list[i] == "AP":
      if stack[i-1] == "PP"
      stack.pop(n_list[i])
  
  elif n_list[i] == "AA":
  
  elif n_list[i] == "A":
      print("NP")
  elif n_list[i] == "P":
      if n_list[i] == n_list[-1]:
          print("PP")

  큰 오산이였다. 두개씩 나누는건 연산에서도, 코드구현에서도 아무런 장점을 가져올 수 없었다.
  

• 문자열의 특성을 살려 일일히 확인한뒤 한번에 빼야겠다는 생각을 했다.

  for _ in range(len(stack) - 3):
      if stack[-1] == "P" and stack[-2] == "A" and stack[-3] == "P" and stack[-4] == "P":
          stack.pop()
          stack.pop()
          stack.pop()
          stack.pop()
          stack.append("P")
          break

  실제로 답은 잘 나왔는데, 백준 제출시 메모리초과가 나왔다. 그 말인 즉슨! 4번을 체크하는 과정이 과하다! 가아닐까?
  

• 그래서 이전에 정리하면서 학습했던 join문을 활용해 보기로 했다.

  for i in range(len(n_list)):
      stack.append(n_list[i])
      
      if len(stack) >= 4 and "".join(stack[-4:]) == "PPAP":
          stack.pop()
          stack.pop()
          stack.pop()
          stack.pop()
          stack.append("P")

  아주 만족스러운 코드가 나오지 않았나.. 실제로 “PPAP” 와 같이 문자열로 작성하는게 불가능하다 생각했는데, 써본뒤에 되는걸 보고, 앞으로의 문제풀이에 엄청나게 유용하게 쓸수있겠다 라는 생각이 들었다.
  

---

코드

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

n_list = list(input())

# print(n_list)

stack = []

# for i in range(len(n_list)):

#     if len(n_list) == 0:
#         print("PPAP")

#     if n_list[i] == "P":
#         if n_list[i] == n_list[-1]:
#             print("PPAP")

#     if n_list[i] == "A":

for i in range(len(n_list)):
    stack.append(n_list[i])
    
    if len(stack) >= 4 and "".join(stack[-4:]) == "PPAP":
        stack.pop()
        stack.pop()
        stack.pop()
        stack.pop()
        stack.append("P")

if len(stack) == 1 and stack[0] == "P":
    print("PPAP")
else:
    print("NP")