[백준 2493번] 탑

박형진·2022년 3월 22일
0

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. 튜플 없이 푼 코드

import sys

n = int(sys.stdin.readline().rstrip())
top = list(map(int, sys.stdin.readline().rstrip().split()))

ans = [0]
stack = [0]
for i in range(1, len(top)):
    while stack and top[stack[-1]] < top[i]:
        stack.pop()
    if not stack:
        stack.append(i)
        ans.append(0)
    else:
        ans.append(stack[-1]+1)
        stack.append(i)
print(' '.join(map(str, ans)))

2. 후기

stack 유형의 문제에서 while 문과 stack의 마지막 항을 비교하는 방식은 자주 사용된다.
receive_tower_idx = len(stack)-1를 어떤 방식으로 사용했는지 기억하자.

++
다시 풀어봤다. 7개월 전보다는 풀이가 나아졌다.

profile
안녕하세요!

0개의 댓글