[ 2304 ] [ Stack ] 창고 다각형

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

2304번: 창고 다각형

 

---

풀이 과정

---

1. 왼쪽 구간을 왼쪽에서 오른쪽으로 진행하면서 최대 높이가 되기 전까지 높이가 높아질때마다 스택에 넣어준다.
   • 구간을 구해주어야 하므로, 스택의 맨 마지막에는 최대 높이가 될 때의 지점도 저장해 준다.
2. 오른쪽 구간을 오른쪽에서 왼쪽으로 진행하면서 최대 높이가 되기 전까지 높이가 높아질때마다 스택에 넣어준다.
   
   • 구간을 구해주어야 하므로, 스택의 맨 마지막에는 최대 높이가 될 때의 지점도 저장해 준다.
3. (1)번과 (2)번 스택을 활용하여 왼쪽 구간과 오른쪽 구간의 넓이를 구해준다.
4. 마지막으로, 최대 높이 구간 넓이를 구해서 더해준다.
   1. 왼쪽 -> 오른쪽으로 찾았을때의 최대 높이가 되는 지점
   2. 오른쪽 -> 왼쪽으로 찾았을 때의 최대 높이가 되는 지점
   3. (2)에서 (1)을 빼준 값에 1을 더한 값이 최대 높이에서의 구간 합이다.

---

소스 코드

---

import sys
from bisect import bisect_left, bisect_right

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
block = []

for _ in range(N):
    L, H = map(int, input().split())
    block.append([L, H])

def rfind(arr, a):
    for i in range(len(arr)-1, -1, -1):
        if arr[i] == a:
            return i
    return -1

def lfind(arr, a):
    for i in range(len(arr)):
        if arr[i] == a:
            return i
    return -1

block.sort(key=lambda x:x[0])
block_value = list(map(lambda x:x[1], block))
max_block_value = max(block_value)
left = []
right = []
p = 0

# 왼쪽 구간 저장
while p < len(block) and block[p][1] != max_block_value:
    if not left:
        left.append(block[p])
    elif left and left[-1][1] <= block[p][1]:
        left.append(block[p])
    p += 1
    
left.append(block[p])

# 오른쪽 구간 저장
p = len(block)-1
while p >= 0 and block[p][1] != max_block_value:
    if not right:
        right.append(block[p])
    elif right and right[-1][1] <= block[p][1]:
        right.append(block[p])
    p -= 1

right.append(block[p])
right.sort(key = lambda x:x[0])

area = 0
# 왼쪽 구간 너비 합
for i in range(1, len(left)):
    area += left[i-1][1] * (left[i][0] - left[i-1][0])

# 오른쪽 구간 너비 합
for i in range(1, len(right)):
    area += right[i][1] * (right[i][0] - right[i-1][0])

# 높이가 가장 큰 부분의 너비 합
lindex = lfind(block_value, max_block_value)
rindex = rfind(block_value, max_block_value)
area += max_block_value * (block[rindex][0] - block[lindex][0] + 1)

print(area)