16120. PPAP - 스택. 파이썬.

사용한 알고리즘 / 자료구조

1. 스택

접근한 방법

1.  스택으로 명세를 그대로 구현한다.

유사한 문제를 이미 풀어보아서 큰 고민 없이 스택으로 풀이했다. 

'9935 문자열 폭발'과 같은 문제다. 

https://programmer-565.tistory.com/18?category=999468 

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

9935번: 문자열 폭발

9935. 문자열 폭발 - 스택. 파이썬

구현한 방법

1. 문자열을 입력받는다. 
2. 스택에 문자열을 채워넣는다. 
3. PPAP가 완성되었을 경우 pop연산을 통해 PPAP => P로 축약한다.

개선 가능한 점

1. 스택을 따로 쓰지 않고 P와 A가 연속적으로 등장하는 정보만으로도 풀 수 있었다. 로직을 잘 생각해보고 그 형태로 구현해봐야겠다. 

 

풀이했을 당시의 백준 티어

2021-11-01, 골드 1

 

실행시간, 메모리, 언어

292ms, 36496kb, Python3

 

# 1. 입력
# 문자열을 입력받는다.
INPUT_STRING = input()

# 2. 선언
# 연산을 위해 스택을 선언한다.
stack = []

# 3. 연산
# 문자열의 모든 문자을 순회하며
for syl in INPUT_STRING:

    # 1) 스택 압축 연산(PPAP -> P)
    # 전제조건 - 현재 문자가 P이고 스택의 길이가 3 이상일 때
    if syl == 'P' and len(stack) >= 3:

        # (1) 스택 압축 가능
        # PPA 가 있다면
        if stack[-3] == 'P' \
                and stack[-2] == 'P' \
                and stack[-1] == 'A':

            # 2개 pop
            stack.pop()
            stack.pop()

        # (2) 스택 압축 불가능
        else:  # 현재 문자를 스택에 삽입. 
            stack.append(syl)

    # 2) 스택을 압축할 수 없다면
    else:  # 현재 문자를 스택에 삽입. 
        stack.append(syl)

# 4. 출력
# PPAP 문자열이라면
if stack == ['P']:
    print('PPAP')

# 아니라면
else:
    print('NP')