Skip to content

Latest commit

 

History

History
341 lines (273 loc) · 9.92 KB

1725.md

File metadata and controls

341 lines (273 loc) · 9.92 KB
Raw

Index

히스토그램

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

예제

입력 1

7
2
1
4
5
1
3
3

출력 1

8

오효근

접근법 (생각의 흐름 설명)

Segment tree에 대한 문제를 공부하기 위해 이 문제를 선택했다. 이후에 설명하겠지만 Python의 한계인 실행 속도 때문에 사실상 segment tree의 풀이가 불가능하다... 그래도 한번 알아보자.

처음에 문제를 접할 때는 two pointer 접근법이 유효한가 생각했지만, 이 문제의 입력 순서가 변경되면 안되기 때문에 정렬할 수 없고 이는 곳 two pointer를 사용할 수 없다는 뜻이다.

일단은 문제 파악을 위해 brute-forece 접근법을 아래와 같이 구현하면 $N$이 최대 100,000 이므로 시간 초과가 발생한다. 아래의 구현은 $O(N^2)$이다.

Brute-force Implementation (6549) 
import sys

read = sys.stdin.readline


def returnSize(L, tar):
    st = 0
    for i in range(tar):
        if L[tar - i - 1] >= L[tar]:
            st += 1
        else:
            break
    for i in range(tar + 1, len(L)):
        if L[i] >= L[tar]:
            st += 1
        else:
            break
    return (st + 1) * L[tar]


while True:
    L = list(map(int, read().split()))
    sc = []
    if L[0] == 0 and len(L) == 1:
        break
    del L[0]
    for i in range(len(L)):
        sc.append(returnSize(L, i))
    print(max(sc))

따라서 자료 구조를 잘 활용하여 $O(N\times\log{N})$과 같이 시간 복잡도를 낮춰야 해결할 수 있다.

상세한 해설

Segment Tree

Segment tree는 완전 이진 tree인 특성을 통해 구간의 query를 낮은 시간 복잡도로 산출할 수 있는 이점이 있다. 따라서 처음 SegmentTree를 초기화 할 때 아래와 같이 정의했다. 재귀적으로 초기화 method _init을 호출하며 자식 node의 값을 self.tree에 입력하는데 여기서 입력되는 것은 구간과 구간 사이의 최소 값 (높이)를 가지는 list의 index이다.

class SegmentTree:
    ...
    def _init(self, node=None, start=None, end=None):
        if node is None and start is None and end is None:
            node = 1
            start = 0
            end = self.length - 1
        if start == end:
            self.tree[node] = start
            return self.tree[node]
        idx1 = self._init(node * 2, start, (start + end) // 2)
        idx2 = self._init(node * 2 + 1, (start + end) // 2 + 1, end)
        if self.values[idx1] <= self.values[idx2]:
            self.tree[node] = idx1
        else:
            self.tree[node] = idx2
        return self.tree[node]

Query를 위한 method인 __call__을 통해 left, right의 입력 시 최소 높이를 가지는 히스토그램의 index를 입력 받을 수 있다.

class SegmentTree:
    ...
    def __call__(self, left, right, node=None, start=None, end=None):
        if node is None and start is None and end is None:
            node = 1
            start = 0
            end = self.length - 1
        if left > end or right < start:
            return -1
        if left <= start and end <= right:
            return self.tree[node]
        idx1 = self(left, right, 2 * node, start, (start + end) // 2)
        idx2 = self(left, right, 2 * node + 1, (start + end) // 2 + 1, end)
        if idx1 == -1:
            return idx2
        elif idx2 == -1:
            return idx1
        if self.values[idx1] <= self.values[idx2]:
            return idx1
        return idx2

마지막으로 large method로 제공된 구간에서 재귀적으로 query를 호출하여 가장 큰 면적을 산출한다.

class SegmentTree:
    ...
    def large(self, start=None, end=None):
        if start is None and end is None:
            start = 0
            end = self.length - 1
        if start == end:
            return self.values[start]
        idx = self(start, end)
        area = (end - start + 1) * self.values[idx]
        if start <= idx - 1:
            tmp = self.large(start, idx - 1)
            area = max(area, tmp)
        if idx + 1 <= end:
            tmp = self.large(idx + 1, end)
            area = max(area, tmp)
        return area
Segment Tree Implementation 
import math
import sys

read = sys.stdin.readline
sys.setrecursionlimit(10**9)


class SegmentTree:
    def __init__(self, values):
        self.values = values
        self.length = len(values)
        size = math.ceil(math.log(self.length, 2) + 1e-9)
        size = 1 << (size + 1)
        self.tree = [0 for _ in range(size)]
        self._init()

    def _init(self, node=None, start=None, end=None):
        if node is None and start is None and end is None:
            node = 1
            start = 0
            end = self.length - 1
        if start == end:
            self.tree[node] = start
            return self.tree[node]
        idx1 = self._init(node * 2, start, (start + end) // 2)
        idx2 = self._init(node * 2 + 1, (start + end) // 2 + 1, end)
        if self.values[idx1] <= self.values[idx2]:
            self.tree[node] = idx1
        else:
            self.tree[node] = idx2
        return self.tree[node]

    def __call__(self, left, right, node=None, start=None, end=None):
        if node is None and start is None and end is None:
            node = 1
            start = 0
            end = self.length - 1
        if left > end or right < start:
            return -1
        if left <= start and end <= right:
            return self.tree[node]
        idx1 = self(left, right, 2 * node, start, (start + end) // 2)
        idx2 = self(left, right, 2 * node + 1, (start + end) // 2 + 1, end)
        if idx1 == -1:
            return idx2
        elif idx2 == -1:
            return idx1
        if self.values[idx1] <= self.values[idx2]:
            return idx1
        return idx2

    def large(self, start=None, end=None):
        if start is None and end is None:
            start = 0
            end = self.length - 1
        if start == end:
            return self.values[start]
        idx = self(start, end)
        area = (end - start + 1) * self.values[idx]
        if start <= idx - 1:
            tmp = self.large(start, idx - 1)
            area = max(area, tmp)
        if idx + 1 <= end:
            tmp = self.large(idx + 1, end)
            area = max(area, tmp)
        return area


if __name__ == "__main__":
    N = int(read())
    L = [0 for _ in range(N)]
    for i in range(N):
        L[i] = int(read())
    st = SegmentTree(L)
    print(st.large())

시간 복잡도는 총 $O(N\times\log{N})$이다. 하지만 동일한 코드를 제출해도 한 번 통과 이후 모두 시간 초과가 발생하는 기이한 현상이 존재한다... 따라서 아래와 같이 Stack으로 구현해야한다.

Stack

Stack의 LIFO (Last-In-First-Out) 특성을 활용하여 해결할 수 있다. stack에 히스토그램의 index를 추가하고 stack의 마지막 index 히스토그램의 높이보다 현재 히스토그램의 높이보다 높다면 넓이를 산정하고 result를 update한다.

import sys

read = sys.stdin.readline

if __name__ == "__main__":
    N = int(read())
    values = [0 for _ in range(N)]
    for i in range(N):
        values[i] = int(read())
    stack = []
    result = 0
    for i in range(N + 1):
        while stack and (i == N or values[stack[-1]] > values[i]):
            height = values[stack[-1]]
            stack.pop()
            width = i
            if stack:
                width = i - stack[-1] - 1
            result = max(result, width * height)
        stack.append(i)
    print(result)

회고

Segment tree를 공부하려했지만 아쉬움이 컸던 문제... 오히려 stack으로 푸는 방법이 생각해내기 어려웠다.

Solution

import sys

read = sys.stdin.readline

if __name__ == "__main__":
    N = int(read())
    values = [0 for _ in range(N)]
    for i in range(N):
        values[i] = int(read())
    stack = []
    result = 0
    for i in range(N + 1):
        while stack and (i == N or values[stack[-1]] > values[i]):
            height = values[stack[-1]]
            stack.pop()
            width = i
            if stack:
                width = i - stack[-1] - 1
            result = max(result, width * height)
        stack.append(i)
    print(result)