백준 2493 탑 / python

문제 : 2493

풀이 point

스택을 활용하여 풀수 있다.
ex)
6 9 5 7 4

1. stack[4]
2. 다음 탑 7을 stack에 삽입하기 전 stack.top을 확인 top이 7보다 작음 -> 수신 가능 4 제거, 7 삽입
3. stack[7] 5 삽입 전 top확인 top이 5보다 큼 -> 수신 불가, 5 삽입
4. stack[7, 5] 9 삽입 전 top 확인 top이 9보다 작음 꺼냄, 7도 작음 꺼냄, 9 삽입
5. stack[9] 6 삽입 전 top 확인 top이 6보다 큼 -> 수신 불가, 6 삽입
6. stack[6, 9]

꺼내지지 못한 stack 속 탑들은 수신 가능한 탑이 없음을 알 수 있음 -1로 치환

수신 가능한 탑들을 꺼낼 때 인덱스를 잘 저장해두었다가 그 인덱스에 맞게 수신 가능한 탑 인덱스를 적어주어야 한다.

풀이 코드

from collections import deque

N = int(input())
tops = list(map(int, input().split()))

S = list() #스택
outs = [0]*N #인덱스 저장

tops.reverse() #뒤집어서 보기

S.append([tops[0], N-1]) #첫번째 탑 (탑, 인덱스)

num = N-1 #몇번째 탑인지

for i in range(1, N):
  length = len(S)
  idx = len(S)-1
  for j in range(length):
    if S[idx][0] <= tops[i]:
      outs[S[idx][1]] = num #해당 인덱스 탑에 수신한 탑 넣어주기
      S.pop()
      idx -= 1
    else: break #탑보다 작은 탑이 있었다면 이미 수신 했을 것이므로
  S.append([tops[i], N-i-1])
  num -= 1


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