[Java+Python]6549번, 히스토그램에서 가장 큰 직사각형

목차

 

분할 정복 단계

 

[Java+Python]2630번, 색종이 만들기

[Java+Python]1992번, 쿼드 트리

[Java+Python]1780번, 종이의 개수

[Java+Python]1629번, 곱셈

[Java+Python]11401번, 이항 계수 3

[Java+Python]2740번, 행렬 곱셈

[Java+Python]10830번, 행렬 제곱

[Java+Python]11444번, 피보나치 수 6

 

문제

 

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 

각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 

예를 들어, 아래 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

 

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

 

입력

 

입력은 테스트 케이스 여러 개로 이루어져 있다. 

각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 $n$이 가장 처음으로 주어진다. $(1 ≤ n ≤ 100,000)$

그다음 $n$개의 정수 $h_1, ..., h_n (0 ≤ h_i ≤ 1,000,000,000)$가 주어진다. 

이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 

모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

 

출력

 

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

 

풀이

 

나름 유명한 것 중 하나라 어디선가 본 기억이 있는 듯한 문제다.

 

주어진 히스토그램을 처음부터 훑으며 만들 수 있는 직사각형 중 가장 큰 것의 넓이를 구하는 문제이다.

 

문제에 대한 이해는 크게 어렵지 않으나 알고리즘 구현과정에서 자꾸 시간 초과가 나서

 

다른 사람의 풀이를 참고하며 다시 풀어야만 했다.

 

문제를 풀이하는 알고리즘의 순서는 다음과 같다.

 

1. 히스토그램을 이루고 있는 직사각형의 개수 $n$을 입력받고 각 직사각형의 높이 $h_1, h_2, ..., h_n$을 height[$n$]에 저장한다.
2. 개별 막대의 인덱스를 저장할 스택을 선언한다.
3. 이어서 막대를 처음부터 순회하며 아래와 같은 작업을 수행한다.
   
   
   1. 스택이 비어있지 않으면서 현재 막대의 높이가 스택의 맨 위 막대의 높이보다 작은 동안 반복한다.
   2. 스택에서 가장 위 인덱스를 꺼내고 해당 막대를 기준으로 직사각형의 넓이를 구한다. 이때 직사각형의 가로길이 $w$는
      맨 위 막대의 인덱스를 이용해 $w = i -$ stack.peek() $- 1$로 정해진다.
   3. 기존 최대 넓이와 비교해서 값을 갱신해 준 뒤 현재 막대의 인덱스를 스택에 추가한다.
   4. 이와 같이 인덱스를 추가하면 스택에 남은 인덱스는 높이를 기준 오름차순으로 정렬된다.
4. 모든 막대를 확인하고 스택에 남은 인덱스를 이용해 스택이 빌 때까지 아래 작업을 반복한다.
   
   
   1. 맨 위 인덱스를 꺼내고 해당 막대를 기준으로 직사각형의 넓이를 계산한다.
   2. 가로길이 $w$를 $n$으로 설정해서 스택이 모두 비워졌을 경우를 고려한다.
   3. 스택에 아직 값이 남아있다면 $w = i -$ stack.peek() $- 1$로 갱신해 넓이를 구하고 갱신해 준다.
5. 결과를 출력한다.

위 과정을 0이 입력될 때까지 반복하면 된다.

 

나도 처음엔 대체 어떻게 푸는 건지 전혀 모르겠었는데, 그림을 그려보고 디버깅을 하면서 배우게 되었다.

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Prob6549 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		while (true) {

			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());

			if (n == 0) {
				break;
			}

			int[] height = new int[n];

			for (int i = 0; i < n; i++) {
				height[i] = Integer.parseInt(st.nextToken());
			}

			ArrayDeque<Integer> stack = new ArrayDeque<>();
			long max = 0;

			for (int i = 0; i < n; i++) {
				while (!stack.isEmpty() && height[stack.peek()] > height[i]) {
					long h = height[stack.pop()];
					int w = i;
					if (!stack.isEmpty()) {
						w = i - stack.peek() - 1;
					}
					max = Math.max(max, h * w);
				}
				stack.push(i);
			}

			while (!stack.isEmpty()) {
				long h = height[stack.pop()];
				int w = n;
				if (!stack.isEmpty()) {
					w = n - stack.peek() - 1;
				}
				max = Math.max(max, h * w);
			}

			sb.append(max).append('\n');
		}

		System.out.println(sb.toString());
	}
}

 

Python

 

import sys

while True:
    n, *height = map(int, sys.stdin.readline().rstrip().split())

    if n == 0:
        break

    height.append(0)
    stack = []
    max_area = 0

    for i in range(n + 1):
        while stack and height[stack[-1]] > height[i]:
            h = height[stack.pop()]
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)

    print(max_area)

 

Performance