P2493. 탑

• 문제: https://www.acmicpc.net/problem/2493

2493번: 탑

설명

하나의 리스트에 넣고 오른쪽부터 시작하여 비교하면서 빼는 방식으로 하면 시간초과가 발생한다.
처음에 리스트에 넣을 때부터 비교하면서 넣는 방법은 어떨까?

주어진 값은 6-9-5-7-4 이다.

• stack = [] : 최댓값을 저장할 스택, 이후에 들어오는 값들과 비교한다.
• result = [] : 결과값을 저장할 스택

일단 신호를 수신받으려면, 최댓값이 크거나 같아야 한다.

1. 스택이 비어있다. 최댓값이 0이다. 6을 수신할 수 있는 탑이 없기 때문에 result에 0을 삽입한다. stack에도 index와 6을 함께 삽입한다.
   • stack = [[0, 6]]
   • result = [0]
2. 9를 확인해보자. 현재 stack의 최댓값(stack[-1][1])은 6이다. 9 > stack[-1][1] 이므로 9도 수신할 수 있는 탑이 없기 때문에 result에 0을 삽입한다. stack에도 index와 9를 함께 삽입한다.
   • stack = [[1,9]]
   • result = [0, 0]

3. 5는 최댓값(stack[-1][1]) 9보다 작기 때문에 수신할 수 있는 탑이 존재한다. 따라서 stack의 최댓값(stack[-1][0]) 인덱스를 가져와서 추가한다.
   +) 인덱스가 0부터 시작하므로 1을 더해줘야한다.
   • stack = [[1, 9], [2,5]]
   • result = [0, 0, 2]

4. 7은 최댓값 5보다 크기 때문에 수신할 수 있는 탑이 존재하지 않는다. 이제 최댓값 5는 제거하자. 어차피 뒤에 오는 탑도 5에게 수신할 수 없기 때문이다. 제거하고 가장 위에 있는 9는 7보다 크기 때문에 수신 가능한 탑이 존재한다.
   • stack = [[1, 9], [3,7]]
   • result = [0, 0, 2, 2]
5. 4는 최댓값 7보다 작기 때문에 수신할 탑이 존재한다.
   • stack = [[1,9], [3,7], [4,4]]
   • result = [0, 0, 2, 2, 4]

코드

from sys import stdin as s

N = int(s.readline().rstrip())
signal = list(map(int, s.readline().rstrip().split()))
stack = []
result = []

for i in range(N):
# stack에 원소가 있을 때만 확인할 수 있다.
while len(stack) > 0:
     # stack에 담긴 값 중 가장 최상위에 있는 것이 더 크면 도달 가능하다. 
     if stack[-1][1] > signal[i]:
         result.append(stack[-1][0] + 1)
            break
        # 이 다음에 값이 와도 가리기 때문에 제거한다.
        else:
         stack.pop()

    # stack에 비어있다면 도달할 수 있는 스신탑이 하나도 없다는 것이다.
if len(stack) == 0:
     result.append(0)
stack.append([i, signal[i]])

for i in result:
print(i, end = ' ')

Reference

• https://jjangsungwon.tistory.com/44