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) 해뒀다가 틀렸다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
