백준 16120 [PPAP] 파이썬

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

 

스택인줄 모르고 풀었을때 막막했다..

 

<시간초과 코드>

# 백준 16120 PPAP

import sys
input=sys.stdin.readline
s=list(map(str,input().rstrip()))
chng_flag=False
succ_flag=True
while len(s)!=1:
    idx=0
    s_end=len(s)-1
    while idx+3<=s_end:
        if idx+3<=s_end and s[idx]=='P' and s[idx+1]=='P' and s[idx+2]=='A' and s[idx+3]=='P':
            if idx+4<=s_end:
                s=s[:idx]+['P']+s[idx+4:]
            else:
                s=s[:idx]+['P']
            chng_flag=True
        idx+=1
        s_end=len(s)-1
    if not chng_flag:
        succ_flag=False
        break
    chng_flag=False
if not succ_flag:
    print('NP')
elif len(s)==1:
    print('PPAP')

 

 

스택을 이용하면 된다는 것을 깨달은 순간 바로 해결됐다.

 

<스택을 이용한 코드>

 

# 백준 16120 PPAP 문제
# 문자열이 "PPAP" 규칙으로만 구성되어 있는지를 스택을 이용해 판별

import sys
input = sys.stdin.readline

# 입력 문자열을 리스트로 변환
s = list(map(str, input().rstrip()))

stack = []       # 스택 초기화
stack_len = 0    # 스택 길이 추적 (최적화를 위한 변수)

# 문자열을 왼쪽부터 한 글자씩 처리
for i in range(len(s)):
    stack.append(s[i])    # 현재 문자를 스택에 추가
    stack_len += 1

    # 스택의 마지막 4글자가 "PPAP" 형태인지 확인
    while stack[-1] == 'P' and stack_len >= 4:
        # 뒤에서 4글자를 pop해서 검사
        fourth = stack.pop()
        third = stack.pop()
        second = stack.pop()
        first = stack.pop()

        # 순서대로 PPAP이면 → 이를 P 하나로 축소
        if first == 'P' and second == 'P' and third == 'A' and fourth == 'P':
            stack_len -= 4
            stack.append('P')  # 축소된 결과 다시 스택에 넣음
            stack_len += 1
        else:
            # 아니라면 다시 순서대로 push하고 더 이상 축소 시도 중단
            stack.append(first)
            stack.append(second)
            stack.append(third)
            stack.append(fourth)
            break  # 더 이상 축소 불가능

# 모든 처리가 끝난 후, 스택에 P 하나만 남았다면 "PPAP 문자열"
if stack_len == 1 and stack[0] == 'P':
    print('PPAP')
else:
    print('NP')  # 아니라면 올바른 PPAP 문자열이 아님