[백준 2493번] 탑

5875 단어 스택백준백준

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


1. 코드

import sys
from collections import defaultdict

n = int(input())
arr = list(map(int, sys.stdin.readline().rstrip().split()))
d = defaultdict(int)
answer = [0]
max_val = arr[0]
stack = [(1, max_val)]
for tower, height in enumerate(arr[1:], 2):
    if height >= max_val:
        max_val = height
        stack.clear()
        stack.append((tower, height))
    else:
        receive_tower_idx = len(stack) - 1
        while stack and stack[-1][1] <= height:
            stack.pop()
            receive_tower_idx -= 1
        stack.append((tower, height))
        d[tower] = stack[receive_tower_idx][0]
for i in range(1, n + 1):
    print(d[i], end=' ')

2. 후기

stack 유형의 문제에서 while 문과 stack의 마지막 항을 비교하는 방식은 자주 사용된다.
receive_tower_idx = len(stack) - 1 값만 잘 찾으면 풀 수 있다.

좋은 웹페이지 즐겨찾기