파이썬 알고리즘 259번 | [백준 16120번] PPAP - 스택을 사용하자 ~~

259. PPAP

1) 어떤 전략(알고리즘)으로 해결?

• 스택 !

2) 코딩 설명

<내 풀이>

import sys

target = str(sys.stdin.readline().strip())
stk = []

for t in target :
    stk.append(t)
    if stk[-1]=="P" and len(stk)>=4 :
        if "".join(stk[-4:])=="PPAP" : 
            for i in range(3) : 
                stk.pop()
                
if "".join(stk)=="P" : 
    print("PPAP")
else :
    print("NP")

---

import sys

target = str(sys.stdin.readline().strip())
stk = []

for t in target :
    # print(stk)
    stk.append(t)
    if stk[-1]=="P" and len(stk)>=4 :
        if "".join(stk[-4:])=="PPAP" : 
            for i in range(3) : 
                stk.pop()
# print("total : ", stk)
if "".join(stk)=="P" : 
    print("PPAP")
else :
    print("NP")

< 내 틀렸던 풀이, 문제점>

시간초과1 2프로

import sys

target = str(sys.stdin.readline().strip())
target.replace('PPAP','P' )
    
while "PPAP" in target and len(str(target))>4 : 
    # print(target)
    for i in range(len(target)-3) :
        if target[i:i+4]=="PPAP" :
            #target[i:i+4].replace("P")
            target = target.replace('PPAP','P',1)
            break
        
if target=="PPAP" : 
    print("PPAP")
else :
    print("NP")

시간초과2 20프로

import sys

target = str(sys.stdin.readline().strip())
target.replace('PPAP','P' )
    
while "PPAP" in target and len(str(target))>4 : 
    target = target.replace('PPAP','P')

if target=="PPAP" : 
    print("PPAP")
else :
    print("NP")

유형 확인
자료 구조
문자열
그리디 알고리즘
스택
이라고 한다.

<반성 점>

• stack pop, push 가 시간을 많이 줄여주니깐 얘네로 replace 처리를 해주면 된다.

<배운 점>

• pop, push 가 O(1) !! 아주 좋아 좋아

스택의 연산에는 다음과 같은 것들이 있다.
push : 스택의 맨 위(뒤)에 데이터를 삽입하는 연산. 시간복잡도 O(1)
pop : 스택의 맨 위(뒤)에서 데이터를 꺼내는 연산. 시간복잡도 O(1)
peek : 스택의 맨 위의 데이터를 보는 연산. 꺼내지 않는다. 시간복잡도 O(1)