백준 16120 PPAP 파이썬

www.acmicpc.net/problem/16120

16120번: PPAP

word = input()
if word == 'P' or word == 'PPAP':
    print('PPAP')
else:
    stack = []
    ppap = ['P','P','A','P']
    for i in word:
        stack.append(i)
        if stack[-4:] == ppap:
            stack.pop()
            stack.pop()
            stack.pop()

    if stack == ppap or stack == ['P']:
        print('PPAP')
    else:
        print('NP')

풀기가 어려운것보다 문제 이해가 어려웠던것 같다.

P와 A로 구성된 문자열이 주어졌을 때,

문자열 내에 PPAP 가 존재하면  P 로 바꾸는 작업을 가능한만큼  계속했을 때 마지막에 남는문자가 P 또는 PPAP 면 'PPAP'를 출력

그게 아니면 'NP'를 출력하는 문제다.

 

알고리즘 분류에서 stack 이라는걸 보고도 한참 생각했다. 

문자열에 있는 문자를 하나씩 stack 에 추가하면서 stack 의 마지막 4글자가 PPAP 라면 P로 바꾸면 되는데 PPAP 중 PAP 만 제거하면 P만 남기 때문에 pop() 을 세번 하도록했고 이렇게 마지막 문자까지 반복하고난 후 stack 에 남은 문자가 PPAP 또는 P 면 PPAP 아니면 NP 를 출력하면 된다.

제대로 된 생각만 떠오르면 구현자체는 아주 쉬운 문제다.

 

처음 stack 안써도 되겠는데? 하면서 시간 초과로 풀었던 소스

word = 'PPPAPAPPPAPPPAPPAPPAPPAPPAPPAPPAPAPAPPAPPAPPAPPPAPAPPAPPAPPAP'
if word == 'P' or word == 'PPAP':
    print('PPAP')
else:
    prev_word_len = len(word)
    while True:
        word = word.replace('PPAP','P')
        
        if prev_word_len == len(word):
            break
            
        prev_word_len = len(word)
    
    if word == 'P' or word == 'PPAP':
        print('PPAP')
    else:
        print('NP')