[정올 1214] 히스토그램

문제

히스토그램이란 보통 분포의 정도를 알기 위해 사각형의 서열을 기준선에 맞춰 늘어놓은 다각형을 말한다.

만약 임의의 수열이 2, 1, 4, 5, 1, 3, 3일 경우 사각형의 너비를 1로 맞추어 히스토그램으로 만들면 다음과 같다.

 

 

 

우리가 하고자 하는 것은 임의의 히스토그램이 주어졌을 때 히스토그램 내에서 사각형으로 이루어진 가장 큰 면적의 크기를 알고자 한다. 

왼쪽 의 히스토그램에서 가장 큰 사각형의 영역은 오른쪽에 밑줄이 쳐진 영역과 같다

 

입력

입력 첫 번째는 히스토그램을 이루는 사각형의 개수 n(n≤100,000)이 입력되고

그 뒤로 히스토그램을 이루는 사각형의 높이가 순서대로 n개 입력이 된다. 

사각형의 높이 k는 0 ≤ k ≤ 1,000,000,000 이다. 사각형의 너비는 모두 1이다.

 

출력

입력된 히스토그램으로 만들 수 있는 사각형의 최대 면적을 출력하라.

---

접근

계속해서 스택과 같은 자료구조를 활용한 문제들을 풀고있다. 적절한 자료구조를 활용하면 코드를 간결하게 짤 수 있고 더 빠르게 동작하는 코드를 작성할 수 있다. 따라서 어떠한 상황에서 어떤 자료구조를 사용할지 파악할 수 있는 것이 중요하다.

 

지금까지 스택을 활용하는 문제를 풀면서 아래와 같은 상황에서 사용되었고 사용된다면 규칙이 있었다.

- 1차원 배열에서 순차적으로 탐색할 때 이전 인덱스의 값을 활용하고자 할 때 사용할 수 있다.

- 스택의 top과 현재 값을 비교하여 push와 pop을 하였다.

 

그렇다면 히스토그램 문제에서는 스택이 어떻게 활용되었는지 알아보자.

히스토그램의 각 사각형의 크기가 2 1 4 5 1 3 3 이라고 할 때 높이가 낮아지는 지점에서 이전의 높이를 기준으로 넓이를 구한다.

즉 1 -> 4 -> 5에서 다음 1이 나오면 높이가 낮아지는 지점이다. 이때 5를 기준으로 넓이를 구하고, 4를 기준으로 넓이를 구한다. 여기서 5를 기준으로 넓이를 구할 때는 높이 5인 사각형으로만 이루어지며 높이가 4인 기준으로 넓이를 구할 때는 4와 5가 해당된다.

따라서 높이가 낮아지는 지점에서 특정 조건에의해 스택에 push 또는 pop 하여 해를 구한다.

 

구현

- 핵심 코드는 아래와 같다.

- 사각형의 높이는 histogram이라는 리스트에 저장하였으며 마지막에 0을 추가하였다.

- 0을 추가한 이유는 낮아지는 지점에서 이전의 넓이를 구하게되는데 0을 추가하지 않으면 마지막 원소인 3에서 끝나 스택에 남아있는 원소에 대해 넓이를 구할 수 없다. 예를 들어 히스토그램 내의 최솟값이 1이라면 1을 기준으로하는 넓이를 구하지 못하고 끝나게된다.

- 이후 스택에 현재 인덱스를 push한다. 

- 스택의 top에 해당하는 인덱스가 가리키는 사각형의 높이가 현재 사각형의 높이보다 크다면 낮아지는 지점이므로 넓이를 구한다.

- 높이는 스택의 top을 기준으로 하고 pop한다.

- 너비는 현재 인덱스에서 현재 스택의 top을 빼주고 -1을 한 번더 빼준다. 이전에 pop을 하여 기준 높이로 설정하였기 때문에 그 다음 top이 너비를 구하기위한 기준이된다.

- 하지만 스택이 비어있다면 현재 인덱스를 기준 너비로 설정한다.

- 이제 넓이를 구하여 비교를 통해 최댓값을 구한다.

for i in range(N+1):
    while stack and histogram[stack[-1]] > histogram[i]:
        j = stack.pop()
        if stack:
            width = i - stack[-1] - 1
        else:
            width = i
        answer = max(answer, histogram[j]*width)
    stack.append(i)

---

전체 코드

import sys
input = sys.stdin.readline

input_data = list(map(int, input().split()))
N = input_data[0]
histogram = []
for i in range(1, len(input_data)):
    histogram.append(input_data[i])
histogram.append(0)

answer = -1
stack = []

for i in range(N+1):
    while stack and histogram[stack[-1]] > histogram[i]:
        j = stack.pop()
        if stack:
            width = i - stack[-1] - 1
        else:
            width = i
        answer = max(answer, histogram[j]*width)
    stack.append(i)
print(answer)