백준 1725번 히스토그램 :: 마이구미

이번 글은 백준 알고리즘 문제 1725번 "히스토그램"을 다뤄본다.

6549번 "히스토그램에서 가장 큰 직사각형" 또한 거의 동일한 문제가 된다.

문제의 접근은 스택을 활용한다.

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

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

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

처음에는 도저히 생각이 나지 않아, 순수하게 접근했다.

시간초과가 발생할 것을 알았지만, 일단 풀어보았다.

단순히, 하나의 막대를 기준으로, 왼쪽 오른쪽에 대해 하나씩 늘려가면서 모든 경우에 대한 넓이를 비교했다.

그 결과, 먼저 생각해봐야할 것이 떠올랐다.

하나의 막대의 높이를 기준으로 만들수 있는 가장 큰 직사각형은 무엇인가?

위 그림에서, 높이가 4, 5인 막대를 보고 얻을 수 있는 정보는 아래와 같다.

1. 높이가 4인 막대는 다음 막대를 포함하여, 너비가 2, 높이가 4인 직사각형을 만들 수 있다.
2. 높이가 5인 막대는 자신을 기준으로는, 왼쪽 오른쪽 막대 모두 높이가 낮기 때문에 다른 막대와 합쳐질 수 없다. 
3. 높이가 5인 막대와 높이가 1인 다음 막대는 높이가 5인 직사각형을 만들 수 없다.

그렇다면, 높이를 오름차순으로 스택에 쌓는다면, 왼쪽으로부터 오른쪽 방향으로 만들 수 있는 경우만 생각하면 된다.

오른쪽 막대(x)를 기준으로 왼쪽 방향의 막대들의 높이는 x보다 낮기 때문이다.

다시 말하면, 왼쪽 막대의 높이를 기준으로 오른쪽 막대와 합쳐서 직사각형을 만들 순 있지만, 반대는 안되기 때문이다.

위 내용으로 코드로 나타내면, 아래와 같이 구현된다. (스택에는 너비를 구하는 과정에서 편의를 위해 인덱스를 저장한다)

for (int i = 0; i < n; i++) {
    while(array[stack.peek()] > array[i]) {
        int height = array[stack.peek()];
        int width = i - stack.peek();
        stack.pop();

        ans = Math.max(ans, width * height);
    }
    stack.push(i);
}

스택에 막대를 하나씩 넣으면서, 스택의 top보다 다음 막대의 높이가 크다면, push한다.

그렇지 않다면, 다음 막대의 높이를 기준으로, 스택을 pop하면서, 넓이를 비교한다.

이 과정에서 스택의 top이 직사각형의 왼쪽 끝이 되고, i가 오른쪽 끝이 된다.

그렇기 때문에, 너비는 (i - 스택의 top) 으로 구한다.

하지만, 이 경우에는 아래와 같은 반례가 존재한다.

높이가 2, 4, 2, 4로 주어졌다면, 답은 8이 나온다.

하지만 위 코드는 왼쪽에서 오른쪽으로만 가정하여 4가 나온다.

세번째 막대, 높이가 2인 막대는 높이가 2, 4인 왼쪽 막대들을 포함할 수 있다.

위에서 언급했듯이, 스택의 top은 직사각형의 왼쪽 끝에 대한 기준으로 활용한다.

이것을 이용하여, 오른쪽에서 왼쪽으로도 포함할 수 있으므로, width 변수를 수정한다.

stack.push(0);
for (int i = 1; i <= n + 1; i++) {

    while(!stack.isEmpty() && array[stack.peek()] > array[i]) {
        int height = array[stack.peek()];
        stack.pop();
        int width = i - stack.peek() - 1;

        ans = Math.max(ans, width * height);
    }
    stack.push(i);
}

양쪽 사이드에 0을 넣으면, 코드의 흐름에 조금 더 맞게 구현될 수 있다.

6549번 "히스토그램에서 가장 큰 직사각형" 문제는 입력 부분만 다르고 동일하다.

주의해야할 점은 높이가 10억까지 주어지기 때문에, 과정 중 int 범위가 넘어갈 수 있다.

그렇기 때문에, long으로 선언을 해야한다.

전체 소스는 아래 Github URL을 참고하길 바란다.

백준 알고리즘 문제 1725번 "히스토그램" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/stack/1725.java