히스토그램에서 가장 큰 직사각형

히스토그램에서 가장 큰 직사각형

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, …, hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

접근방법

처음에 단순 코딩으로 풀었다가 시간초과가 나서 세그먼트 트리를 공부하였다

[세그먼트 트리 2042]([구간 합 구하기

Sicoree](https://sicoree.github.io/posts/2042/))

해당문제를 세그먼트 트리를 공부하여 해결하였고, 요번문제에 적용시켰다

처음에는 어떻게 적용시켜야 하는지 생각이 안나서 구글의 도움을받아 최소 높이의 인덱스를 구하는것을 세그먼트 트리를 활용하게 되었다.

최소높이와 인덱스를 저장해둘 세그먼트 트리를 구현한 후,

구간별로 최소높이를 찾고, 그 인덱스를 기준으로 좌우를 쪼갈라 다시 최소높이를 찾는것을 반복한다

최소높이만 있으면 넓이는 구해지기때문에 이후는 해결하기 쉬웠다

아직 자세하게 설명이 안되므로 조금더 공부한 후 다듬도록 하겠다 ..

코드 1 (시간초과)

## 삽질 ( 시간초과 )
# while True:
#     arr = deque(list(map(int, input().split())))
#     H = arr.popleft()

#     if H == 0:
#         break

#     hq = deque(set(arr))
#     result = 0

#     while hq:
#         h = hq.popleft()

#         max_cnt = 0
#         cnt = 0
#         for idx in range(H):
#             if arr[idx] >= h:
#                 cnt += 1
#             else: 
#                 if cnt > max_cnt:
#                     max_cnt = cnt
#                 cnt = 0

#         if cnt > max_cnt:
#             max_cnt = cnt

#         if result < max_cnt * h:
#             result = max_cnt * h

#     print(result)

코드 2 (성공)

import sys

# 없으면 에러
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

# 인덱스까지 다루기 때문에 min, idx 를 쌍으로 가지고 있어야 함
def minIndex(left, right):
    if left[0] < right[0]:
        return left
    else:
        return right

# 구간별 최솟값 세그먼트 트리
def init(node, left, right):
    if left == right:
        arr[node] = [tmp[left], left]
        return arr[node]

    mid = (left + right) // 2
    left_node = init(node * 2, left, mid)
    right_node = init(node * 2 + 1, mid + 1, right)
    arr[node] = minIndex(left_node, right_node)
    return arr[node]

# node, from, to, left, right
# from, to = 현 노드의 범위
# left, right = 구해야하는 범위
def sol(node, f, t, left, right):
    if right < f or t < left:
        return [1000000001, -1]

    if left <= f and t <= right:
        return arr[node]

    mid = (f + t) // 2
    left_node = sol(node * 2, f, mid, left, right)
    right_node = sol(node * 2 + 1, mid + 1, t, left, right)
    return minIndex(left_node, right_node)

# node, from, to
# from, to = 현 노드의 범위
def divide(f, t):
    if f == t:
        return tmp[f]
    if f > t:
        return -1

    min, idx = sol(1, 0, N - 1, f, t)
    a = divide(f, idx - 1)
    b = divide(idx + 1, t)
    c = min * (t - f + 1)
    return max(a, b, c)

while True:
    # N, *tmp = list(map(int, input().split()))
    tmp = list(map(int, input().split()))
    N = tmp.pop(0)

    if N == 0:
        quit()

    arr = [[0] * 2 for _ in range(4 * N)]

    init(1, 0, N - 1)
    print(divide(0, N - 1))

코드 3 (스택)