백준 2304 창고 다각형 Python

🐸 문제 정보

2304번: 창고 다각형

 

🤖 알고리즘

스택

(이라고 적혀있지만 구현에 가깝다)

 

⏱️ 풀이 시간

30.25m

 

📝 풀이

보자마자 스택 문제인 것은 알았지만, 스택보다는 구현에 가까운 문제였다.

가장 높은 지점을 기준으로, 왼쪽 오른쪽에서 최대값은 의미가 없다는 것을 알아야했다.

때문에 입력 값에서 가장 높은 지점의 인덱스를 찾은 후, 그 지점을 기준으로 왼쪽 오른쪽 각 1회씩 탐색하면서 스택 형태로 값을 더해주면 되는 문제였다.

 

문제에서 모든 인덱스에 h가 있는 것은 아니기 때문에 defaultdict를 이용해서 시간복잡도를 조금이라도 줄이고자 했다.

 

🧑‍💻 나의 답

# pypy3

import sys
from collections import defaultdict
input = sys.stdin.readline

n = int(input().rstrip())
blocks = defaultdict(int)
m, ml, mh = 0, 0, 0
for _ in range(n):
    l, h = list(map(int, input().rstrip().split()))
    blocks[l] = h
    if mh < h:
        mh = h
        ml = l
    m = max(m, l)

res = 0
temp = 0

for i in range(ml + 1):
    if temp < blocks[i]:
        temp = blocks[i]
    res += temp

temp = 0
for i in range(m, ml, -1):
    if temp < blocks[i]:
        temp = blocks[i]
    res += temp

print(res)