소스코드
import sys
input = sys.stdin.readline
N = int(input().strip())
tops = [(idx + 1, height) for idx, height in enumerate(map(int, input().strip().split()))]
stack = []
result = []
for i in range(N):
idx, height = tops[i]
# 스택에 들어갈 값보다 작은 값들은 모두 제거
while stack and stack[-1][1] < height:
stack.pop()
if not stack:
result.append(0)
else:
result.append(stack[-1][0])
stack.append((idx,height))
# 결과 출력
sys.stdout.write(' '.join(map(str, result)) + '\n')
Python
복사
풀이
•
선형탐색을 해야겠다는 생각을 했습니다(출력 순서가 그렇기 때문에)
•
input 데이터를 enumerate를 이용해서 약간 변환한 이유는 결과가 수신탑의 인덱스 + 1이기 때문입니다.
•
스택에 쌓아보는 식으로 그림을 그려봤는데, 스택이 맞다고 생각이 들어 더 풀어봤습니다.
◦
인덱스 0부터 차례대로 스택에 append합니다.
◦
스택에 있는 탑의 높이가 현재 선형탐색하며 들어갈 값보다 작은 경우엔 어차피 수신을 못하므로 다 빼버립니다.
▪
만약 스택이 비어있다면, 수신할 탑이 없다는 뜻이므로 0을 결과 배열에 추가합니다.
▪
스택에 값이 있다면, 해당 탑의 인덱스를 결과 배열에 추가합니다.
•
결과 배열을 ‘ ‘으로 join해서 출력합니다 → 끝!