[알고리즘][파이썬] 백준 16120번 - PPAP

---

처음 떠올렸던 접근 방법

1. 문자를 앞에서부터 읽어가며 P또는 A가 각각 나올 수 없는 타이밍에 나오면 NP를 출력하고 종료한다.
2. 끝까지 종료되지 않았을 경우, PPAP를 출력한다.

개선된 접근 방법

1. 문자를 앞에서부터 읽어가며 스택에 추가하고, 스택의 최근 4개 인덱스의 값이 PPAP가 형성되면 4개의 인덱스를 제거(pop)하고 P를 추가한다.
2. 스택에 남아있는 요소가 P또는 PPAP일 경우, PPAP를 출력하고 그렇지 않다면 NP를 출력한다.

---

최종 입력 코드

w = input()
stack = []
ppap = ["P", "P", "A", "P"]
for i in range(len(w)):
    stack.append(w[i])
    if stack[-4:] == ppap:
        for _ in range(4):
            stack.pop()
        stack.append("P")
if stack == ppap or stack == ["P"]:
    print("PPAP")
else:
    print("NP")

---

처음에 스택을 생각 못하고 단순 문자열+그리디 문제인 줄 알았다.
그래서 그냥 if 문을 여러번 반복해서 하드코딩 스타일로 제출했더니 당연히 오답판정..

알고리즘 분류를 보곤 스택 문제 였다는 걸 알고 머리가 띵 했다.
아직도 문제를 보고 어떠한 방식으로 풀어야할지 선택지들이 감이 잘 안잡히는게 넘 슬프다ㅠ

if stack[-4:] == ppap:

리스트 슬라이싱도 가끔 쓰려고 하면 헷갈린다.
문제를 풀 때 감을 잃지 않게 유형들을 이것저것 번갈아가며 풀어야겠다.