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

문제 유형을 보면
세그먼트 트리, 스택, 분할 정복 이렇게 3가지로 분류된다.
풀 수 있는 방법이 다양한 것 같다.
히스토그램은 너비는 같고, 높이가 다른 직사각형 여러개가 아래 부분을 맞춰서 옆으로 붙어 있는 모양인데 이 붙어있는 모양에 포함되는 가장 큰 직사각형 모양의 넓이를 찾는 것이다.

직사각형의 너비는 1로 같고, 입력으로는 높이가 차례로 주어지는데... 모르겠다. 그냥 바로 풀이를 봐야겠다.

baekjoon online judge blog에 백준님이 풀이를 잘 써놓으셔서 이해는 어느정도 됐는데, 내가 다시 써보려니 그리 쉽지는 않다. 백준님이 소개하는 방법으로는 두 가지가 있는데, 바로 분할 정복(+세그먼트 트리)을 이용하는 방법과 스택을 이용하는 방법 이렇게 두 가지이다.

먼저 분할 정복(+세그먼트 트리)으로 풀어보자.
히스토그램을 구성하는 각 직사각형을 하나씩 봤을 때, 그 직사각형의 높이를 가지는 가장 큰 직사각형은 그 직사각형을 기준으로 양쪽으로 직사각형을 확장하면서, 그 직사각형의 높이보다 작은 직사각형이 나오기 직전까지 확장하면 만들 수 있다.
그런데 이 과정을 모든 직사각형에 대해 일일이 해보려고 하면 O(n제곱)의 시간이 걸릴 것이다. 하지만 이것을 하나의 아이디어와 분할 정복을 이용한다면 좀 더 쉽게 할 수 있다.
각 직사각형의 높이를 가지는 가장 큰 직사각형을 찾을 때, 일단 가장 높이가 작은 직사각형부터 찾기 시작한다. 가장 높이가 작은 직사각형의 경우 양쪽으로 보면서 그 직사각형의 높이보다 작은 직사각형을 찾을 필요가 없다. 높이가 가장 작기 때문에 히스토그램의 왼쪽 끝과 오른쪽 끝까지의 직사각형이 그 높이를 가지는 가장 큰 직사각형이 될 것이다.

근데 여기서 의문이 들 것이다. 높이가 가장 작은 직사각형은 그렇다 치고 그럼 다른 높이를 가지는 것은 어떻게 할 것인가? 바로 여기서부터 분할 정복이다. 높이가 가장 작은 직사각형을 기준으로 분할할 수 있다. 분할을 한 후에 분할된 각 히스토그램에서 가장 높이가 작은 직사각형을 찾아서 그 높이를 자기는 가장 큰 직사각형은 역시 그 분할된 히스토그램의 양쪽 끝까지이다. 그리고 또 그 직사각형을 기준으로 분할하는 작업을 해 나간다. 바로 이렇게 분할함으로서 양쪽으로 확장해서 찾을 필요 없이 바로바로 해당 높이를 가지는 가장 큰 직사각형을 찾을 수 있다.
그리고 당연한 것이지만 설명하자면 히스토그램을 분할하면서 가장 작은 높이를 가진 직사각형 기준으로 분할하는 것은 어차피 그 높이보다 큰 높이를 가지는 직사각형을 만들 때는 더 작은 높이는 필요가 없기 때문이다.

자 그런데 문제가 하나 있다. 이렇게 분할을 해도 결국 그 분할된 히스토그램에서 최소값을 찾아야 한다. 생각해보면 분할 정복은 이분 탐색이랑은 좀 달라서 최악의 경우에는 최대 O(n)의 분할을 할 수도 있으므로 최소값을 직접 찾는다면 O(n제곱)의 시간복잡도를 가질 수 있다. 여기서 이 문제를 해결해줄 것이 바로 segment tree이다. segment tree를 이용하면 구간의 최소값을 O(log n)만에 찾을 수 있으므로 O(nlog n)에 해결할 수 있다.

한 번 구현해 봐야겠다.
주의할 점으로는 segment tree에 저장해야할 값은 구간의 최소값이 아닌 구간의 최소값의 index이다. (분할할 때 필요한 것은 index이고, 또한 index만 알아도 최소값은 바로 알 수 있기 때문에)
막상 구현해보니 segment tree를 구현할 때 구간의 최소값이 아닌 index를 넣다보니 조금 헷갈리기도 하고 실제로 실수도 해서 런타임에러도 났다. 결국 AC를 받았다.

이제 stack을 이용해 푸는 법을 알아보겠다.
각 직사각형 마다 그 높이를 가지는 가장 큰 직사각형은 그 직사각형을 기준으로 양쪽으로 살펴보면서 처음으로 높이가 작은 직사각형 직전까지가 되는데, 이 것을 stack을 이용해서 O(n)만에 구할 수 있는 것 같다.

일단 맨 앞에서부터 직사각형x를 stack에 넣는데, 현재 stack의 top값보다 작다면 stack의 top값을 높이로 하는 가장 큰 정사각형의 오른쪽 끝이 x-1까지라는 것을 알 수 있다. 그렇다면 왼쪽끝은 어떻게 알까? stack에는 top값보다 큰 경우에만 push하기 때문에, top값 바로 직전에 들어가있는 값이 y이면 y+1이 왼쪽끝을 나타내는게 된다.
그리고 히스토그램의 맨 끝에 도달할 경우에는 오른쪽 끝은 히스토그램의 맨 끝으로 놓고, top값의 직전에 들어간 값을 보면서 왼쪽 끝을 정할 수 있다.


출처 : 백준님 풀이, 강의 자료, https://www.acmicpc.net/blog/view/12