[Java+Python]1725번, 히스토그램

목차

 

문제

 

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

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

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 

 

아래 그림의 빗금 친 부분이 그 예이다. 

 

이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

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

 

입력

 

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. 

N은 히스토그램의 가로 칸의 수이다. 

다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 

각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

 

출력

 

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

 

풀이

 

까마득한 예전에 분할정복을 이용해 풀었던 문제와 같은 문제이다.

 

차이가 있다면 이번에는 스택을 이용해서 풀어야 하는 것인데, 솔직히 문제만 읽고는 감도 오지 않았다.

 

그래서 검색하고 남의 답을 보고 하면서 한 땀 한 땀 진행하느라 시간이 많이 든 문제이다.

 

해서 스택으로 이 문제를 효율적으로 푸는 방법은 대략 아래와 같다.

 

먼저, 스택에는 높이가 계속해서 증가하는 막대의 인덱스를 저장한다. 즉, 스택의 위에 있는 막대는

 

언제나 스택의 아래에 있는 막대보나 높이가 높거나 같다. 같을 수도 있다는 조건을 명시하기 위해

 

이를 '오름차순'이 아닌 '비내림차순'이라 표현하기도 한다.

 

따라서 진행 중 새 막대가 스택의 가장 위 막대보다 높이가 높거나 같으면, 이 막대는 바로 스택에 추가된다.

 

반대로 새 막대가 가장 위 막대보다 낮거나 같다면, 현재 스택의 최상단에 있는 막대로 만들 수 있는

 

가장 큰 직사각형의 넓이를 계산한 뒤, pop 하고 결괏값을 갱신한 뒤 새 막대를 제거하는데,

 

이 과정을 새 막대가 스택의 최상단 막대보다 높거나 같을 때까지, 혹은 스택이 빌 때까지 반복한 뒤에 새 막대를 스택에 추가한다.

 

이런 식으로 가능한 모든 방법을 스택을 이용해 계산함으로써 주어진 막대로 만들 수 있는 직사각형의 최대 넓이를 구할 수 있다.

 

계속해서 코드를 보자.

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

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

		int n = Integer.parseInt(br.readLine());
		int[] height = new int[n + 1];

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

		ArrayDeque<Integer> stack = new ArrayDeque<>();

		int result = 0;

입력의 첫 줄(막대의 개수)을 입력받아 n에 넣고, 이를 기반으로 height 배열을 선언, 이후의 입력값을 이용해 배열을 초기화한다.

 

이어서 어레이덱을 이용해 스택을 만들고, 결괏값을 저장할 result를 0으로 초기화한다.

		for (int i = 0; i <= n; i++) {
			while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
				int h = height[stack.pop()];
				int w;

				if (stack.isEmpty()) {
					w = i;
				} else {
					w = i - stack.peek() - 1;
				}
				result = Math.max(result, h * w);
			}
			stack.push(i);
		}

위에서 설명한 로직이 간결하게 구현된 코드이다.

 

먼저 스택이 비어있거나, 새로운 막대가 스택의 최상단 막대보다 높이가 높을 경우는 해당 인덱스를 바로 push를 한다.

 

그리고 while문을 이용해, 스택이 비어있지 않고, 새로운 스택이 최상단 막대보다 높이가 낮은 동안 다음 과정을 반복한다.

 

• 스택의 가장 위에 있는 요소의 인덱스를 이용해 높이 h를 정한다.
• 이어서 가로길이 w를 설정하는데, 스택이 비어있으면 i, 비어있지 않다면 i - stack.peek() - 1을 할당한다.
  이는 지금까지의 막대의 분포를 볼 때 해당 높이로 만들 수 있는 가장 넓은 가로길이를 할당하는 것이다.
• result를 현재 값과 방금 구해진 값을 비교해 갱신한다.

이렇게 최상단 막대보다 높이가 같거나 높아지면 해당 인덱스를 스택에 넣는다.

		System.out.println(result);
	}
}

결괏값을 출력한다.

 

솔직히 스택에서 pop 하고 push 하면서 직사각형의 최대 넓이를 구하는 과정이

 

직관적으로는 아직도 잘 이해가 되지 않는다.

 

생각이 꼬여있는 건지 몇 번을 따라가도 아직도 길을 잃을 때가 많으니..

 

역시 플래티넘 문제는 아직 무리인가..

 

Java

 

package BackJoon;

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

public class Prob1725 {

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

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

		int n = Integer.parseInt(br.readLine());
		int[] height = new int[n + 1];

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

		ArrayDeque<Integer> stack = new ArrayDeque<>();

		int result = 0;

		for (int i = 0; i <= n; i++) {
			while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
				int h = height[stack.pop()];
				int w;

				if (stack.isEmpty()) {
					w = i;
				} else {
					w = i - stack.peek() - 1;
				}
				result = Math.max(result, h * w);
			}
			stack.push(i);
		}

		System.out.println(result);
	}
}

 

Python

 

import sys

n = int(sys.stdin.readline().rstrip())
height = [int(sys.stdin.readline().rstrip()) for _ in range(n)] + [0]
stack = []
result = 0

for i in range(n + 1):
    while stack and height[stack[-1]] >= height[i]:
        h = height[stack.pop()]
        w = 0

        if not stack:
            w = i
        else:
            w = i - stack[-1] - 1

        result = max(result, h * w)

    stack.append(i)

print(result)

 

Performance