[백준 | 골드4] 16120: PPAP(스택)

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

문제

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를 출력한다.

예제 입력 1

PPPAPAP

예제 출력 1

PPAP

예제 입력 2

PPAPAPP

예제 출력 2

NP

 

문제 설명

문자열을 P에서 시작
문자열 내의 P를 PPAP로 바꾸는 과정을 반복

문자열 P에서 시작
P'PPAP'AP -> PPAP -> 성공
'PPAP'APP -> PAPP -> 실패 -> NP

 

문제풀이 전략

방법 1 —> 시간초과

한번 0번 인덱스부터 PPAP를 만다는 경우 현재 인덱스에서부터 자르고,

PPAP를 단어 다음부터 잘라서 새로운 단어 만들기

새로운 단어를 가지고 반복문다시 돌기

word = input()

#반복 되는 word 길이가 4랑 같은 경우
#반복 되는 단어가 PPAP랑 같은 경우
while len(word) > 4 or word != "PPAP": 
    #총 길이가 4보다 작은 경우
    if len(word) <= 4 :
        break

    #word 안에 PPAP 단어가 없는 경우 종료
    if "PPAP" not in word :
        break

    for i in range(len(word)) :
        #print(i)
        ##i가 P인 경우 찾기, i부터 4글자 확인해서 PPAP 인 경우 찾기
        if word[i] == 'P' and word[i:i+4] == "PPAP" :
            #찾은 인덱스가 PPAP를 만족한다면, 그 앞 뒤로 잘라서 새로운 단어 만들어주기
            word = word[:i+1] + word[i+4:]      
            break            #한번 시행했으니 뒤는 더이상 볼필요 없음
        

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

 

방법2

스택으로 풀기

스택으로 풀기 스택에 무조건 한글자씩 넣는다. 스택에 맨 위부터 들어간 단어가 PPAP인지 확인한다 만약 PPAP이면 처음 P를 제외하고 3개를 POP 시켜준다. 넣을 때마다, TOP과 4개를 검사해서 PPAP가 맞는지 확인하자

import sys
sys.stdin = open("백준_16120_PPAP.txt", "r")

word = input()
stack = []
ppap = ['P', 'P', 'A', 'P']

for w in word :
    stack.append(w)                     #무조건 하나씩 스택에 넣는다.
    print("스택",stack)

    if len(stack) >= 4 : 
        print("끝에 4개",stack[-4:])
        if stack[-4:] == ppap :
            print("뽑습니다!!")
            stack.pop()
            stack.pop()
            stack.pop()
            print("3개 뽑은 스택", stack)

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

방법 1과 다른 점 방법 1은 PPAP로 바꾸고 또 인덱스 0부터 시작해서 다시 반복한다 그러므로 반복이 엄청 많아진다 -> 비효율적

방법 2는 일단 word만큼만 for문이 돌아간다. 딱 len 만큼만 반복이 되고, len의 마지막까지 돌아갔을 떄, 멈추므로 효율적이다.