[백준] 2493번 탑

거북이·2023년 4월 2일
0

백준[골드5]

목록 보기
46/82
post-thumbnail

💡문제접근

  • 처음엔 문제를 잘 이해하지 못해서 시간이 좀 오래 걸렸다.
  • 통신연구소의 레이저 송신기에서 보내는 레이저의 방향은 오른쪽에서 왼쪽이다.
  • 테스트케이스를 예제로 설명하면 다음과 같다.
    • 첫 번째 탑의 높이인 6은 수신받을 탑이 존재하지 않으므로 0이 된다.
    • 두 번째 탑의 높이인 9에서 레이저를 보내면 받을 탑이 없으므로 0이 된다.
    • 세 번째 탑의 높이인 5에서 레이저를 보내면 두 번째 탑(9)에서 받을 수 있으므로 2가 된다.
    • 네 번째 탑의 높이인 7에서 레이저를 보내면 두 번째 탑(9)에서 받을 수 있으므로 2가 된다.
    • 다섯 번째 탑의 높이인 4에서 레이저를 보내면 네 번째 탑(7)에서 받을 수 있으므로 4가 된다.

💡코드(메모리 : 172792KB, 시간 : 708ms)

import sys
input = sys.stdin.readline

N = int(input())
Top_list = list(map(int, input().strip().split()))
stack = []
result = []

for i in range(N):
    while stack:
        if stack[-1][1] > Top_list[i]:
            result.append(stack[-1][0] + 1)
            break
        else:
            stack.pop()
    if not stack:
        result.append(0)
    stack.append([i, Top_list[i]])
print(' '.join(map(str, result)))

💡소요시간 : 34m

0개의 댓글