[알고리즘] 스택 & 백준(탑, PPAP)

* Deque을 활용하여 스택을 구현하는게 더 효율적이다.

[파이썬/Python] Collections - Deque

---

1. 2493: 탑

문제

실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라. 

 

[풀이]
1) enumerate를 활용하여 인덱스와 해당하는 값을 하나씩 stack에 현재 문자 하나를 넣어준다.

 

2) tower가 highest보다 크면 해당 tower를 highest로 바꿔주고, 튜플 형태의 해당 타워의 인덱스와 값을 stack에 넣어준다. 

 

3) tower가 highest보다 크기 때문에, 즉 송신하는 타워가 수신 받는 타워보다 크기 때문에 수신 받는 타워가 없다. 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력해야하기 때문에 answer에 0을 넣어주고, continue 한다.

 

4-1) stack의 가장 마지막에 들어간 튜플의 값(stack[-1][1])이 tower보다 크면, 
stack의 가장 마지막에 들어간 튜플의 인덱스(stack[-1][0])를 answer 리스트에 넣어주고 break를 한다.

4-2) stack의 길이가 0이면 수신하는 탑이 존재하지 않기 때문에 answer에 0을 넣어주고 break를 한다.

4-3) stack의 가장 마지막에 들어간 튜플의 값(stack[-1][1])이 tower보다 작으면, pop()으로 마지막 tower를 빼준다. (tower보다 큰 애가 stack의 젤 위에 올 때까지)

5) *answer를 이용하여 answer 리스트의 각 원소(각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호? 인덱스?)들을 출력한다.

[Python] 가장 파이썬스러운 enumerate 활용법

아래 함수를 enumerate 사용함으로써, for문을 하나 덜 쓸 수 있는 것 같다.

# 2493: 탑

import sys
sys.stdin = open('input.txt', 'r')
N = int(sys.stdin.readline())   # 탑의 수
# 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호/수신하는 탑 존재 X => 0
# [6, 9, 5, 7, 4]
# [0, 0, 2, 2, 4]

stack = []
answer = []
highest = 0
for idx, tower in enumerate(map(int, input().split())):
    if tower > highest:
        highest = tower
        stack.append((idx+1, tower))
        answer.append(0)
        continue
    
    while True:
        if stack[-1][1] > tower:
            answer.append(stack[-1][0])
            stack.append((idx+1, tower))
            break
        elif len(stack) == 0:
            answer.append(0)
            break
        # tower보다 큰 애가 stack의 젤 위에 올 때까지...
        else:
            stack.pop()

print(*answer, sep=" ")

---

2. 16120: PPAP

문제

bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다. PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다.

• P는 PPAP 문자열이다.
• PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.

예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다.

문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라.

 

[풀이]

1) 하나씩 stack에 현재 문자 하나를 넣어준다.

2) 지금까지 stack에 들어온 문자들 중 마지막 4글자가 PPAP인지 검사한다.

3-1) PPAP가 맞다면 pop()을 4번해서 없애주고, 

4) stack에 다시 P를 append 해준다.

=> 여기서, 3-1), 4)을 합쳐서 해줘도 괜찮다.

3-2) PPAP가 맞다면 pop()을 3번 해준다.  

 

문제도 정확히 이해했고, 생각한 로직도 맞았지만 stack에 넣은 "PPAP"를 확인하는 방법을 내가 생각한 방식대로 구현하지 못 했다. 또한 그냥 리스트로 append(), pop()을 하는 바람에 시간초과가 났기 때문에 스택을 쓸 때 from collections import deque을 활용하여 모듈을 이용하면 더 빠른 연산이 가능할 것 같다.

=> stack에 넣은 "PPAP"를 확인하는 방법은 리스트를 join 함수를 활용해 문자열로 만들어서 stack[-4:]으로 마지막 4개 글자가 "PPAP"인지 확인하는 방식으로 풀었다. 

[Python] 리스트를 join 함수 활용하여 문자열로 만들기

이 문제에서 또 놓치기 쉬운 부분은 'P는 PPAP 문자열이다.'이다. P는 문자열의 개수가 1개이고, stack에 들어있는 첫 번째 글자가 'P'이기 때문에 and 조건을 활용하여 두 조건 모두 만족해야지만 PPAP를 만들 수 있다. 

# 16120: PPAP
# PPAP 문자열에서 P하나를 PPAP로 바꾼 문자열이 PPAP 문자열이다.

import sys
from collections import deque
sys.stdin = open('input.txt', 'r')
inputs = deque(list(input().rstrip()))
stack = []

# 1. 하나씩 stack에 현재 문자 하나를 넣어준다.
# 2. 지금까지 stack에 들어온 문자들 중 마지막 4글자가 PPAP인지 검사한다.
# 3. PPAP가 맞다면 pop()을 4번 해서 없애주고
# 4. stack에 다시 P를 append 해준다.

while inputs:
    a = inputs.popleft()
    stack.append(a)
    if stack and ''.join(stack[-4:]) == "PPAP":
        for i in range(3):
            stack.pop()

if stack:
    # stack에 문자 P만 있을 경우(P는 PPAP 문자열이다.)
    if len(stack) == 1 and stack[0] == 'P':
        print("PPAP")
    else:
        print("NP")
else:
    print("NP")

 

도움을 주신 분들

From WH

From NL