2493: 탑

풀이 시간

• 24m
• 자료구조문제도 간간이 풀어줘야지

구현 방식

• stack을 이용해서 레이저 신호를 수신하는 탑을 알아낼 수 있도록 구현하였다 (stack에 탑의 높이와 해당 탑의 index를 넣어줌)

• N만큼 for문을 돌면서 building을 앞에서부터 순서대로 처리해준다

• 매 회마다 stack의 tail에 building에 대한 값을 넣어주는데, 발사한 레이저 신호를 수신한 탑의 번호를 출력해야하므로 '탑의 index'와 '탑의 높이'를 모두 넣어줘야한다

• 매 회마다 stack이 빌 때까지 while문을 돌면서, 1) stack의 tail에 있는 탑의 높이가 현재 building[i] 보다 높다면 result에 tail에 있는 탑의 인덱스를 넣어주고 break 해줌 2) 그렇지 않다면 tail에 있는 탑을 pop

코드

import sys

N = int(sys.stdin.readline()[:-1])
building = list(map(int, sys.stdin.readline()[:-1].split()))
stack = []
result = []
for i in range(N):
    flag = False
    while stack:
        if stack[-1][1] > building[i]:
            result.append(stack[-1][0] + 1); flag = True
            break
        else:
            stack.pop()
    if not flag: result.append(0)
    stack.append((i, building[i]))

for i in range(N):
    print(result[i], end=" ")
print()

결과

• stack을 이용하여 O(N)의 시간복잡도로 해결할 수 있다