[백준] 16120 : PPAP (Python)

 

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

 

---

 

아이디어

해당 문제는 스택의 대표적인 유형 문제인 괄호 넣기와 유사하다. 문자열 내의 특정 문자열을 대체하는 유형이다. 즉, 역과정을 통해 PPAP 문자열인지 검토하는 방법을 통해 문제의 알고리즘을 설계할 수 있다.

다시 말해, 'PPAP' 문자열을 'P'로 대체 및 반복하여, 마지막에 'PPAP' 및 'P'가 남으면, PPAP 문자열이라고 정답 처리를 할 수 있다. 대체하고 반복한다는 의미를 다음의 예제를 통해 파악할 수 있다.

대체 및 반복의 의미 파악을 위한 예제 과정

문자열 내의 PPAP를 찾아 P로 대체하는 과정을 시각화하였고, 대체된 전체 문자열을 다시 이용하여 다음 PPAP를 찾는 것이다. 이런 과정을 거치면 초기 문자열의 길이보다 줄어들게 되고, PPAP 문자열이라면 PPAP 또는 P만 남게 될 것이다.

 

그렇다면, 어떤 방식을 통해 PPAP를 P로 대체하는지 알아보자. 먼저, 선술한 내용을 다시 살펴보자.

•  '대체된 전체 문자열을 다시 이용하여, 다음 PPAP를 찾는 것이다.'

이 내용을 다시 말하자면, PPAP를 P로 대체시 중첩되는 PPAP 문자열이 존재할 수 있다는 의미이다. 중첩의 의미를 다음과 같이 시각화하였다.

중첩의 의미

이런 식으로 중첩된 PPAP가 존재할 수 있기 때문에, 순차적으로 앞에서부터 PPAP를 발견 시 P로 대체해야 한다. 또한, 그렇게 대체된 전체 문자열을 이용하여, 다음 PPAP를 찾아야 한다.

 

이러한 과정을 스택 자료구조를 활용하면, 한 번의 For문으로 전체 문자열을 탐색할 수 있다. 즉, O(n) 시간으로 해결 가능하다는 것이다. 스택을 어떻게 활용해야 하는가? 다음의 예제를 탐색하는 과정을 담은 시각화 사진을 통해 알아보자.

예제

예시 문자열 아래의 각 번호는 탐색 순서를 나타낸다. 이제 자세한 탐색 과정을 살펴보자.

탐색 과정

먼저 우리가 찾고자 하는 문자열은 'PPAP'이므로, 스택의 길이가 4인지 체크하는 조건이 필요하다. 그렇기 때문에, 4번 탐색 과정까지는 스택에 현재 탐색 대상 문자를 삽입만 하게 된다.

이후 6번째 탐색 과정에서 보이는 것처럼, 스택의 마지막 원소 4개가 'PPAP'라면 스택의 해당 원소들을 모두 삭제하고 P를 스택에 추가(대체)한다. 이후, 대체된 전체 문자열은 스택이 되므로, 현재 탐색 원소를 마지막에 삽입한다.

그렇게 탐색이 종료되면, 스택에 남아있는 원소들이 'PPAP' 또는 'P'인지를 확인하여, 정답 처리를 해주면 된다.

 

정리하자면, 스택의 append와 pop의 조건은 다음과 같다.

• IF len(stack) < 4, THEN 현재 탐색 원소 append
• IF (len(stack) >= 4) and (stack[-1:-5:-1] == 'PPAP'), THEN according to next step.
  • pop()을 4번 진행
  • 문자 'P' append
  • 현재 탐색 원소 append
  • (개선) PPAP를 3번만 pop을 하면 어처피 P만 남기 때문에, 위의 두 과정(pop*4번, P삽입)을 pop*3번으로 요약 가능.
• IF (len(stack) >=4) and (stack[-1:-5:-1] != 'PPAP'), THEN 현재 탐색 원소 append

필자는 P의 개수 및 A의 개수를 체크하여 위의 로직을 따르도록 프로그램을 구현하였다. 다시 말해, 괄호 넣기 문제처럼 왼쪽 괄호 개수와 오른쪽 괄호 개수를 각각 체크하는 것처럼 진행하였다. 로직은 같으므로, 이를 감안하여 정답 코드를 참고하길 바란다.

 

정답 코드

# https://www.acmicpc.net/problem/16120
# PPAP
# 스택,문자열

# 역과정. (like 괄호문제)

input=__import__('sys').stdin.readline

S=input()[:-1]
stk=[]
cnt_p,cnt_a=0,0

for i in S:
    if cnt_p<3:
        stk.append(i)
        if i=='P':cnt_p+=1
        else:cnt_a+=1
    # 현재까지의 문자 중에서 PPAP가 존재하면
    elif cnt_a>0 and stk[-1:-5:-1]==['P','A','P','P']:
        for _ in range(4): # PPAP 제거
            t=stk.pop()
            if t=='P':cnt_p-=1
            else:cnt_a-=1
        stk.append('P');cnt_p+=1 # P 삽입
        stk.append(i) # 현재 탐색 원소 삽입
        if i=='P':cnt_p+=1
        else:cnt_a+=1
    else:
        stk.append(i)
        if i=='P':cnt_p+=1
        else:cnt_a+=1

# 길이가 최종적으로 줄여진 전체 문자열 검사
if stk==['P','P','A','P'] or stk==['P']:
    print('PPAP')
else:
    print('NP')