Baekjoon 16120

29 Jul 2023 in Study / Computer science on Baekjoon 16120

Stack

Baekjoon 16120

Description

bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다.

PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다.

P는 PPAP 문자열이다.
PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.
예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다.

문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라.

Input

첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.

Output

첫 번째 줄에 주어진 문자열이 PPAP 문자열이면 PPAP를, 아닌 경우 NP를 출력한다.

Example I & O

Input
PPPAPAP

Output
PPAP

Input
PPAPAPP

Output
NP

My solution

from collections import deque
import sys

print = sys.stdout.write

input = sys.stdin.readline
String = input()[:-1]

if String == "P":
    print("PPAP")

else:

    filterQueue = deque()
    processStack = deque()


    for i in range(len(String)):
        processStack.append(String[i])

    flag = False
    while len(processStack) != 0:
        currentChar = processStack.pop()
        filterQueue.append(currentChar)
        if len(filterQueue) >= 4:
            if filterQueue[-1] + filterQueue[-2] + filterQueue[-3] + filterQueue[-4] == "PPAP":
                for i in range(4):
                    filterQueue.pop()
                if len(processStack) == 0 and len(filterQueue) == 0:
                    flag = True
                    break
                processStack.append("P")

    if flag:
        print("PPAP")
    else:
        print("NP")   

• Sketch

Use 2 stacks

processStack : save string

filterQueue : This is for filtering PPAP (PPAP → P)

• Code Analysis
  

if String == "P":
    print("PPAP")

Condition : P → result : PPAP

---

for i in range(len(String)):
    processStack.append(String[i])

flag = False

First, string should be saved into processStack

flag : True == PPAP, False == NP

When is flag True? : Both stacks are empty

---

while len(processStack) != 0:
    currentChar = processStack.pop()
    filterQueue.append(currentChar)
    if len(filterQueue) >= 4:
        if filterQueue[-1] + filterQueue[-2] + filterQueue[-3] + filterQueue[-4] == "PPAP":
            for i in range(4):
                filterQueue.pop()
            if len(processStack) == 0 and len(filterQueue) == 0:
                flag = True
                break
            processStack.append("P")

If 4 chars from top is PPAP in filterQueue,
remove them from filterQueue and append P into processStack
Both stacks are empty after removing 4 chars from filterQueue → That PPAP (consists of these 4 chars) is last one → Input string is PPAP String

---

Best answer

answer