[백준/Python] [Gold IV] PPAP - 16120

[Gold IV] PPAP - 16120

문제 링크

성능 요약

메모리: 161764 KB, 시간: 236 ms

분류

자료 구조(data_structures), 그리디 알고리즘(greedy), 스택(stack), 문자열(string)

문제 설명

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

 

---

👉나의생각

문제 이해가 잘안되서 문제이해하는데 조금 걸렸다. 알고리즘문제들이 점점 한번에 이해하기 어려워져~

이걸 왜 스택으로 풀라하는건지...한참고민했넹

하지만 결국 P는 PPAP문자열이고, P 하나를 PPAP로 바꾼 문자열도 PPAP문자열이라는 점이 핵심인것 같다.

P인지 PPAP인지만 알면되는거 아냐!?!

 

 

📍나의 풀이

word = input()
stack = []

if word == "P" or word == "PPAP":  # 기본조건에 맞춰 출력/ P는 PPAP 문자열이다 /PPAP는 PPAP 문자열이다.
    print("PPAP")
else:
    ppap = ["P", "P", "A", "P"]
    for i in word:  # 입력값을 돌면서 스택에 넣기
        stack.append(i)
        if stack[-4:] == ppap:  # 뒤에 4글자가 ppap면 P만 남기자
            # print(stack[-4:])['A', 'P', 'A', 'P']
            stack.pop()
            stack.pop()
            stack.pop()
    if stack == ppap or stack == ["P"]:  # 스택안에 요소가 ppap거나 P라면 PPAP출력
        print("PPAP")
    else:  # 아니라면 NP출력
        print("NP")

먼저 입력값이 P이거나 PPAP이면 PPAP를 출력하게 하였고,

다른조건으로는 ppap라는 리스트를 만들어서 요소를 P,P,A,P로 주었다.

그다음 입력값을 돌려서 일단 stack리스트에 넣고 뒤에4글자가 ppap라면 p만 남게 pop을 이용해 빼줬다.

그러고 stack이 ppap와 같거나 p라면 PPAP를 출력 아니면 NP를 출력하게 하였다.

 

 

골드문제지만 사람들이 많이 안풀어서 골드간것같다..실버따리가 더 어려운뎅..오늘은..(알고리즘스터디하면서 문제를 랜덤으로 푸는중)