[Python] 백준 2493번 탑

문제

https://www.acmicpc.net/problem/2493

입력

• 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

• 첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

입력 예제

5
6 9 5 7 4

출력 예제

0 0 2 2 4

문제 풀이

• 완탐을 진행하면 시간초과가 발생하므로 stack을 사용하여 풀이해야한다.
• stack을 생성해서 0번째 인덱스를 넣는다.
• 이후 stack에 값이 있고, top[stack[-1]]이 현재 탐색하는 값보다 작다면 레이저를 수신할 수 없으므로 pop한다.
• 이 과정을 모두 반복한 후에도 stack에 값이 남아있다면 레이저를 수신할 수 있는 탑이 있는 것이므로 result에 해당 index를 넣은 후, 최종적으로 result를 출력한다.

코드

n = int(input())
top = list(map(int,input().split()))
stack = []
result = [0] * n

for i in range(n):
    # stack의 최상단 원소 값이 더 큰지 확인
    while stack and top[stack[-1]] <= top[i]:
        stack.pop()
    # stack이면 더 큰 값의 인덱스가 저장되어있으므로 result에 할당
    if stack:
        result[i] = stack[-1] + 1
    stack.append(i)

print(*result)