[백준알고리즘/2493번/파이썬] 탑

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

2493번: 탑

 

문제: 탑의 갯수와 높이가 주어졌을 때, 각 탑에서 쏘는 레이저를 수신할 수 있는 탑의 번호를 구하는 문제

 

풀이 방법: 스택

 

풀이 코드:

import sys
from collections import deque

n = int(input())
array = list(map(int, sys.stdin.readline().rstrip().split()))
stack = deque()
ans = [0]*n

for i in range(n):
    while stack:
        if stack[-1][0] >= array[i]:
            ans[i] = stack[-1][1]+1
            stack.append([array[i],i])
            break
        else:
            stack.pop()

    stack.append([array[i],i])
    
print(' '.join(map(str,ans)))

 

 

풀이 설명:

문제 풀이에 활용한 것은 두가지 입니다.

1. 탑에 대한 정보를 스택에 담는다.

2. A라는 탑 뒤에 A보다 높은 B라는 탑이 있을 경우, B 이후에 있는 탑의 레이저는 받지 못한다. 따라서, 스택에서 pop 한다.

 

풀이에 핵심이 되는 코드를 보겠습니다.

 

for i in range(n):
    while stack:
        if stack[-1][0] >= array[i]:
            ans[i] = stack[-1][1]+1
            stack.append([array[i],i])
            break
        else:
            stack.pop()

    stack.append([array[i],i])

 

먼저 stack에는 [높이, index]를 담습니다.

 

빈 스택이 아닐 경우, while 문이 돌아가게 됩니다.

 

조건 1) 앞선 탑에 높이가 현재 보다 높은 A라는 탑이 있다면 그 타워에 레이저가 닿을 것이므로, A 타워의 index를 저장해줍니다.

그리고 A 타워 뒤에 A보다 낮은 타워가 있을 수 있으므로 A 타워의 높이와 index를 스택에 저장해줍니다.

 

반대로, 뒤에 나온  B라는 탑보다 스택에 있는 A라는 탑이 더 낮다면  A에 닿을 레이저는 모두 B라는 탑에 닿아 더이상 필요가 없으므로 pop 하게 됩니다.

 

문제에 주어진 예시로 설명을 해보자면 다음과 같습니다. (6 9 5 7 4)

 

처음 6은 그대로 스택에 저장되게 됩니다.

stack = [[6,0]]

ans = [ 0, 0, 0, 0, 0]

 

그 다음 9를 만나게 되면, 반복문을 돌게 됩니다.

따라서 스택에 있는 6은 그대로 pop되고 9가 들어가게 됩니다.

stack = [[9,1]]

ans = [ 0, 0, 0, 0, 0]

 

5를 만나게 되면, 반복문을 도는데 이번에는 9 가 5보다 크므로 5 또한 스택에 담기게 됩니다. 그리고 9에 레이저가 닿으므로 9의 index를 저장하게 됩니다.

stack = [[9,1] , [ 5, 2 ]]

ans = [ 0, 0, 2, 0, 0]

 

7을 만나게 되면, 반복문에서 5보다 7이 더 크므로 5는 pop 되게 되고 다시 5와 같이 스택에 담기게 됩니다. 물론 레이저는 9에 닿으므로 9의 index를 저장하게 됩니다.

stack = [[9,1] , [7,3]]

ans = [ 0, 0, 2, 2, 0]

 

마지막으로 4를 만나게 되면, 4는 9로 가지 않아도 7에 닿습니다. 따라서, 7의 index를 저장하게 됩니다.

stack = [[9,1] , [7,3] , [4,4]]

ans = [ 0, 0, 2, 2, 4]