BOJ 2493 탑

https://www.acmicpc.net/problem/2493
시간 1.5초, 메모리 128MB
input :

• N (1 <= N <= 500,000)
• N개의 탑들의 높이

output :

• 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력

탑의 개수는 50만 개이다.. 이 탑들을 모두 뒤에서 부터 헤아리면서 찾으면, 최악의 경우 50만 * 50만의 경우의 수를 가지게 된다...
어떻게 줄여야 하는 가???

앞에서 부터 비교를 할 방법은 없을까?
뭐 언제나 그렇듯 블로거들을 찾아보고, 스택을 이용하게 되었다.

스택에 (idx, height)를 저장해서 하나씩 꺼내며 비교를 하다가, 자기보다 크거나 같은 건물을 찾으면, 이 idx + 1 한 것을 정답에 추가하는 것이다.

그리고 이렇게 찾은 건물 2개 다를 스택에 다시 넣어서 비교 대상으로 여긴다.

import sys

n = int(sys.stdin.readline())
heights = list(map(int, sys.stdin.readline().split()))
temp = [(0, 0)]
ans = []

for idx, item in enumerate(heights):
    flag = 0

	# 모든 temp에 들어있는 건물들을 비교하다가.
    while len(temp) > 0:
        compare_idx, compare_height = temp.pop()
        # 크거나 같은 것을 찾은 경우에 break로 빠져나감.
        if compare_height >= item:
            flag = 1
            break

    if flag:
    # compare 변수에 이 값들이 남아 있으니까 다시 temp 변수에 넣어주고,
    # 답을 업데이트 해준다.
        temp.append((compare_idx, compare_height))
        ans.append(compare_idx + 1)
    else:
        ans.append(0)
	
    # 현재까지의 값도 temp에 넣어주어서 비교대상이 되도록 한다.
    temp.append((idx, item))

for item in ans:
    print(item, end=" ")

맨 처음에 출력 하는거 그냥 빨리 보려고
print(item) 해뒀다가 틀렸다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ