[Python] 백준2493번 : 탑

💡문제

백준 2493번 문제 링크

🍀풀이

코드

import sys
input = sys.stdin.readline

n = int(input())

tower = list(map(int, input().strip().split()))
pos = [0] * n	# 각 탑이 신호를 받는 탑의 위치
stack = []		# 탑의 인덱스를 저장

for i in range(n):
    while stack:
        if tower[i] > tower[stack[-1]]:
            stack.pop()
        else:
            pos[i] = stack[-1] + 1
            break
    stack.append(i)
    
print(*pos)

문제를 보고 뭔가 쉽게 풀 수 있을거 같았는데 시간을 보니까..1.5초라 내 생각대로는 안풀릴거 같았다...
어떻게 풀어야하나 생각하다가 정말 머리가 안돌아가서 의혁님과 서현님 코드를 봤다. 의혁님이 설명을 자세하게 해주셔서 그대로 베껴왔다!(당당)

아래의 코드를

if tower[i] > tower[stack[-1]]:
    stack.pop()
else:
	pos[i] = stack[-1] + 1
    break

• 현재 탑(tower[i])이 스택의 마지막 탑(tower[stack[-1]])보다 높으면?
  - 스택에서 pop()
  - 왜냐하면 현재 탑이 더 크면 기존 스택에 있는 탑들은 신호를 받을 수 없기 때문!

• 현재 탑이 더 작거나 같으면?
  - position[i] = stack[-1] + 1 → 해당 인덱스+1 값을 저장
  - 현재 탑이 stack[-1]에 있는 탑에게 신호를 받을 수 있음.
  - break로 루프 종료.
  

이렇게 이해를 했다. 근데 비슷한 문제가 나오면 잘 생각해서 풀 수 있을까? 심히 걱정...