[BOJ] 백준 1725번 히스토그램 - Stack 풀이 (Java)

#1752 히스토그램

난이도 : 플레 5 

유형 : 자료구조/ 스택

1725번: 히스토그램

▸ 문제

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

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

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

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

▸ 입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

▸ 출력

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

 

문제 풀이  

6549번 히스토그램에서 가장 큰 직사각형과 동일한 문제이다. 이미 전에 풀었던 문제이지만 또 푸는 이유는 6549번은 세그먼트로 풀이했다면 해당 문제는 스택으로 풀이하려고 한다.

📚 조건

• N (1 ≤ N ≤ 100,000)
• 각 칸의 높이는 0 <= 높이 <= 1,000,000,000

구상

1. index를 기준으로 해당 히스토그램을 탐색을 한다.
2. i를 탐색할 때 현재 새로 들어온 직사각형의 높이(arr[i])와 이전(arr[s.peek()]i-1)에 위치한 높이와 비교한다. 
   1. arr[i] >= arr[s.peek()] 새로 들어온 직사각형의 높이가 더 클 경우, 이전보다 지금 새로 들어온 직사각형에서 큰 직사각형의 넓이가 나올 수 있으므로 while문을 패스한다
   2. arr[i] < arr[s.peek()] 이전에 위치한 직사각형 높이가 더 클 경우 큰 직사각형이 이전에 위치할 확률이 높으므로 넓이를 구해준다.   ☛ arr[i]보다 작거나 같은 값이 나올 때까지 반복
3. 2번의 연산이 끝났으면(최대 넓이를 구했거나 패스했거나) i를 stack에 넣어준다.

스케치

1번 로직

index를 기준으로 탐색하는 것은 세그먼트 트리 풀이와 마찬가지로 해당 탐색은 높이만 탐색하는 것이 아니라 구간을 탐색하는 것이기 때문에 히스토그램의 index와 높이 두 값이 모두 필요하기 때문이다. 따라서, Stack에는 직사각형의 높이가 아닌 index의 정보가 들어간다.

 

2번 로직

논리는 이렇다. Stack에 2-1) 새로 들어오는 직사각형의 높이가 현재 직사각형의 높이보다 클 경우 값을 저장해준다. 그러면 자연스럽게 새로들어오는 직사각형들의 높이는 이전보다 높다는 것을 알 수 있다.

 

그리고나서 이젠 2-2) 새로 들어오는 직사각형이 현재 직사각형의 높이보다 작다면 이전의 직사각형이 더 크다는 소리이므로 이전까지 쌓아왔던 내림차순(Stack은 후입선출이므로)으로 되어있는 직사각형 높이들을 모두 조회해준다.

 

단, 새로 들어오는 직사각형의 높이보다 큰 경우까지만 조회해준다. 이유는 높이가 같거나 낮으면 새로 들어오는 직사각형과 같이 넓이를 구할 수 있는 직사각형이기 때문이다.

 

시뮬레이션

예제에서 제공한 히스토그램을 가지고 시뮬레이션을 돌려보자.

arr : [ 2 1 4 5 1 3 3 ] 

 

 

1) i=2, stack에 값을 push하다가 새로 들어오는 직사각형이 현재 직사각형의 높이보다 작다면 계산을 해준다. 이전 직사각형의 높이를 계산해준다. 앞으로 계산할 이유가 없는 직사각형이이므로 계산해주고 stack에서 제거한다. 

1번 직사각형 : s.pop(); 

 

 

 

2) i=5, 이번에도 마찬가지로 계산해주면 된다. arr[2] == arr[5]이므로 3번까지만 계산해주고 while문을 종료시킨다.

3번 직사각형 : s.pop(); 

4번 직사각형 : s.pop(); 

 

 

2) i=8,마지막까지 조회가 완료되었다면 여태까지 stack에 남아있는 계산하지 못한 직사각형들을 모조리 계산해준다.

7번 직사각형 : s.pop(); , 6번 직사각형 : s.pop(); 

5번 직사각형 : s.pop(); , 2번 직사각형 : s.pop(); 

 

 

 

로직 상태표

i	stack 상태	top	arr[top] (이전 높이)	arr[i] (새로운 높이)	action (넓이 = 높이 * 밑변)
1	[ 0 ]	0	arr[0] = 0	arr[1] = 2	s.push(1);
2	[ 1 0 ]	1	arr[1] = 2	arr[2] = 1	s.pop(); arr[1] < arr[2]   넓이 = arr[1]* 1 = 2;
3	[ 2 0 ]	2	arr[2] = 1	arr[3] = 4	s.push(3);
4	[ 3 2 0 ]	3	arr[3] = 4	arr[4] = 5	s.push(4);
5	[ 4 3 2 0 ]	4	arr[4] = 5	arr[5] = 1	arr[3~4] < arr[5] 넓이1 = arr[4] * 1 = 5; 넓이2 = arr[3] * 2 = 8; arr[5] == arr[2] stop
6	[ 5 2 0 ]	5	arr[5] = 1	arr[6] =3	s.push(6);
7	[6 5 2 0]	6	arr[6] = 3	arr[7] = 3	s.push(7);
8	[7 6 5 2 0]	7	arr[7] = 3	arr[8] = 0 (끝)	arr[7~0] < arr[8]  남은 모든 넓이를 구해준다. 넓이1 = arr[7] * 1 = 3; 넓이2 = arr[6] * 2 = 6; 넓이3 = arr[5] * 5(8-3) = 5; 넓이4 = arr[2] * 7(8-1) = 5;
8	0	0	0	0	종료

 

반복문 n+1까지 돌려주는 이유

n+1까지 탐색해주는 이유는 마지막에 큰 직사각형이 존재할 수 있기 때문이다. 

 

n까지 탐색할 경우 반례는 다음과 같다.

n = 7,  arr = [ 2 1 2 4 1 4 4 ]

마지막 [4 4]의 직사각형이 가장 큰 직사각형인데 i까지 탐색할 경우 해당 직사각형의 넓이를 구하지 않고 탐색을 종료하게 된다. 그래서 arr의 크기도 n+2까지 해준다.

 

풀이 코드

import java.io.*;
import java.util.Stack;

public class Main {

	static int n;
	static int[] arr;	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n =  Integer.parseInt(br.readLine());
		arr = new int[n+2];
		for(int i=1; i<n+1; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Stack<Integer> s = new Stack<>();
		s.push(0);
		int ans =0;
		for(int i=1; i<n+2; i++) {
			while(!s.isEmpty()) {
				int top = s.peek();
				if(arr[top] <= arr[i]) break;
				s.pop();
				ans = Math.max(ans, arr[top]*(i-s.peek()-1));
			}
			s.push(i);
		}
		System.out.println(ans);
	}
}

 

세그먼트 트리 풀이 보러가기