[BOJ] 백준 6549번 히스토그램에서 가장 큰 직사각형 (Java)

#6549 히스토그램에서 가장 큰 직사각형

난이도 : 플레 5

유형 : 자료 구조/ 세그먼트 트리/ 분할 정복

6549번: 히스토그램에서 가장 큰 직사각형

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤

www.acmicpc.net

▸ 문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

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

▸ 입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

▸ 출력

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

문제 풀이

어렵다. 세그먼트 트리를 공부했기 때문에 자신있게 접근했지만 여러 시행착오를 겪었다.

10만개의 직사각형의 구간합을 모든 경우의 수를 계산해서 찾아내려고 한다. 만약 1개의 직사각형의 최대 높이를 가져서 모든 곳을 탐색하는 최악의 경우에는 10만번 * 10만번의 연산이 이뤄지므로 브루트포스 탐색을 하면 안된다.

이 때 필요한 것이 분할정복과 세그먼트 트리를 사용한 구간 합 풀이이다. (세그먼트 트리 공부하러가기)

세그먼트 트리를 사용하면 O(N)인 선형 탐색 효율성을 트리의 장점을 활용하여 O(logN)으로 줄여준다.

또한 분할 정복이 필수이다. 전체 히스토그램의 길이(0~n-1)를 시작으로 최적화된 방식으로 구간을 분할하여 탐색해줘야 한다.

따라서 해당 문제 풀이에 있어 핵심은 세그먼트 트리에 대한 개념과 최적화된 분할정복 설계이다.

구상

히스토그램의 직사각형 높이에 관한 데이터를 저장한 배열 arr을 가지고 세그먼트 트리를 생성한다.
히스토그램을 길이가 1인 직사각형부터 n인 직사각형까지 모든 직사각형을 최적의 방법으로 분할시킨다. - Divide
각 하위 문제를 재귀적(stack) 방식으로 나누어 각 하위 구간의 넓이를 세그먼트 트리를 사용하여 구한다. - Conquer, 세그먼트 트리
해당 하위 문제들에서 구한 값들을 비교하면서 최댓값을 도출해낸다. - Combine

스케치

∙ 1번 로직 - 세그먼트 트리 생성

말 그대로 구간 합을 넣으면 안된다. 해당 풀이에서 구간 합 트리의 사용목적이 뭔지 파악해야 한다.

해당 문제에서는 분할 정복을 할 때 그 구간에서의 가장 작은 높이의 값을 필요로 한다. 그런 다음 해당 값과 그 구간의 길이를 곱해서 영역의 크기를 구할 것이다. 따라서 세그먼트 트리의 값은 그 구간에서의 최소 높이를 가지는 배열 index를 저장할 것이다.

→ index를 저장해주는 이유는 아래 로직을 보면 알게된다.

∙ 2번 로직 - 구간 분할하여 해당 구간의 최대 넓이 구하기

분할이 중요하다. 같은 크기의 2개 부분 배열로 분할하는 방식은 사용하면 안된다.

🙅‍♂️같은 크기의 2개의 부분 배열로 분할하면 안되는 이유 ↓(더보기 클릭)

세그먼트 트리를 최근에 공부했으니 쉽게보고 의식의 흐름대로 풀이를 하였다가 중간에 막혔다. 나는 구간 합 트리의 초기화를 해당 구간의 배열의 최소 높이 값을 저장했다.

그런데 그 이제 분할정복하면서 탐색을 하는데 무작정 반반 갈라서 나누면 미처 탐색하지 못하는 구간이 있었다.

~~초기 분할 방법 : mid = (start+end)/2;~~

반례) 7 2 1 2 4 1 4 4

> 최댓값은 빨간 동그라미가 있는 부분인 8인데, 7을 출력한다. (5~6)부분을 탐색하지 못했다.

분할의 기준으로 삼는 지점은 해당 구간의 최소 높이를 가지는 index이다. 만약 구간 0 ~ 6인 히스토그램이 최소 높이가 1이고 그 해당 직사각형의 index가 2라면 다음 분할 구간은 2를 기준으로 0~1과 3~6으로 분할시켜줘야 한다. 그래야 다음 최소 높이을 가지는 직사각형들을 찾아 최대 영역의 크기를 구할 수 있게 된다.

→ 내가 필요한 데이터는 배열 index와 해당 값(높이)이다. 트리에 높이를 저장하면 높이의 데이터만 가져올 수 있지만 index를 저장하면 index와 높이 두 개의 데이터를 모두 쉽게 가져올 수 있다.

시뮬레이션

위의 같은 크기의 2개의 부분 배열로 분할하면 안되는 이유 반례를 가지고 직접 시뮬레이션을 돌려보자.

1) 처음 구간 0~6에서의 영역의 최소 높이는 1이다. 그래서 크기가 7인 직사각형이 나온다.

2) 0~6에서 1의 높이를 가진 1번 직사각형을 기준으로 분할을 하였다. 구간(0~0), 구간(2~6)에서도 세그먼트 트리를 이용하여 최소 높이를 구한 다음 1)번 방식과 똑같이 크기를 구하면 각각 2와 5가 나온다.

3) 구간(0~0)은 더 이상 분할이 안된다. 구간 (2~6)을 분할하면 아래와 같이 크기가 4, 8인 직사각형을 구할 수 있다.

∙ 4번 로직 - 각 구간의 넓이를 비교하여 최대 넓이 구하기

재귀는 stack방식으로 후입선출이기 때문에 모든 탐색을 마치고 나서 합치는 과정에서 하위문제부터 상위문제까지 차근차근 넓이 비교를 쉽게 해줄 수 있다.

코드 설명

✔︎ 1번 로직 코드 - 세그먼트 트리 생성

각 구간마다 최소의 높이를 가지는 index를 저장해주는 세그먼트 트리를 생성한다

size = getTreeSize();
tree= new int[size];
init(arr,1,0,n-1);

static int getTreeSize() {
		int h = (int)Math.ceil(Math.log(n)/Math.log(2)) +1;
		return (int)Math.pow(2, h);
	}
	
static void init(int[] arr, int node, int start, int end) {
		if(start == end) {
			tree[node] = start;
		}
		else {
			int mid = (start + end) /2;
			init(arr, node*2, start, mid);
			init(arr, node*2+1, mid+1, end);
			
			if(arr[tree[node*2]] < arr[tree[node*2+1]]) {
					tree[node] = tree[node*2];
			}
			else {
					tree[node] = tree[node*2+1];
			}
		}
	}

✔︎ 2~4번 로직 코드 - 구간 분할하여 해당 구간의 최대 넓이 구해서 비교하기

최소의 높이를 가지는 Index를 기준으로 분할을 하여 각 영역의 크기를 비교해준다.

한 쪽의 범위가 벗어나는 경우 다른 쪽 탐색 값을 리턴해주면 된다.

if(left > end || right < start) return -1;

if(leftNode == -1) return rightNode;
else if(rightNode == -1) return leftNode;

	static long getMax(int left, int right) {
		int n = arr.length;
		int m = query(0,n-1,left,right,1);
		
		long area = (long)(right - left +1)*(long)arr[m];
		if(left<= m-1) {
			long tmp = getMax(left, m-1);
			if(area < tmp) {
				area = tmp;
			}
		}
		
		if(m+1 <= right) {
			long tmp = getMax(m+1, right);
			if(area < tmp) {
				area = tmp;
			}
		}
		return area;
	}
	
	static int query(int start, int end, int left, int right, int node) {
		if(left > end || right < start) return -1;
		if(left <= start && end <= right) {
			return tree[node];
		}
		
		int mid = (start+end)/2;
        
		// 왼쪽부분탐색
		int leftNode = query(start, mid, left, right, node*2);
		// 오른쪽부분탐색
		int rightNode = query(mid+1, end, left, right, node*2+1);
		
		if(leftNode == -1) {
			return rightNode;
		}
		else if(rightNode == -1) {
			return leftNode;
		}
		else {
			if(arr[leftNode]<=arr[rightNode])
				return leftNode;
			else 
				return rightNode;
		}
	}

풀이 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	static int n,size;
	static int[] arr, tree;	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		while(true) {
			String s = br.readLine();
			if(s.equals("0")) break;
			
			st = new StringTokenizer(s);
			n = Integer.parseInt(st.nextToken());
			
			arr = new int[n];
			for(int i=0; i<n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			size = getTreeSize();
			tree= new int[size];
			init(arr,1,0,n-1);
			System.out.println(getMax(0,n-1));
		}
	}
	
	static int getTreeSize() {
		int h = (int)Math.ceil(Math.log(n)/Math.log(2)) +1;
		return (int)Math.pow(2, h);
	}
	
	static void init(int[] arr, int node, int start, int end) {
		if(start == end) {
			tree[node] = start;
		}
		else {
			int mid = (start + end) /2;
			init(arr, node*2, start, mid);
			init(arr, node*2+1, mid+1, end);
			
			if(arr[tree[node*2]] < arr[tree[node*2+1]]) {
					tree[node] = tree[node*2];
			}
			else {
					tree[node] = tree[node*2+1];
			}
		}
	}
	static long getMax(int left, int right) {
		int n = arr.length;
		int m = query(0,n-1,left,right,1);
		
		long area = (long)(right - left +1)*(long)arr[m];
		if(left<= m-1) {
			long tmp = getMax(left, m-1);
			if(area < tmp) {
				area = tmp;
			}
		}
		
		if(m+1 <= right) {
			long tmp = getMax(m+1, right);
			if(area < tmp) {
				area = tmp;
			}
		}
		return area;
	}
	
	static int query(int start, int end, int left, int right, int node) {
		if(left > end || right < start) return -1;
		if(left <= start && end <= right) {
			return tree[node];
		}
		
		int mid = (start+end)/2;
		int leftNode = query(start, mid, left, right, node*2);
		int rightNode = query(mid+1, end, left, right, node*2+1);
		
		if(leftNode == -1) {
			return rightNode;
		}
		else if(rightNode == -1) {
			return leftNode;
		}
		else {
			if(arr[leftNode]<=arr[rightNode])
				return leftNode;
			else 
				return rightNode;
		}
	}
	
}

스택 풀이 보러가기

'Dot Algo∙ DS > PS' 카테고리의 다른 글

[BOJ] 백준 1655번 가운데를 말해요 (Java) (0)	2021.06.18
[BOJ] 백준 14502번 연구소 (Java) (0)	2021.06.18
[BOJ] 백준 17069번 파이프 옮기기 2 (Java) (0)	2021.06.17
[BOJ] 백준 2042번 구간 합 구하기 (Java) (0)	2021.06.16
[BOJ] 백준 2098번 외판원 순회 (Java) (0)	2021.06.15

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

그릿 속의 해빗

[BOJ] 백준 6549번 히스토그램에서 가장 큰 직사각형 (Java)

#6549 히스토그램에서 가장 큰 직사각형

▸ 문제

▸ 입력

▸ 출력

문제 풀이

구상

스케치

∙ 1번 로직 - 세그먼트 트리 생성

∙ 2번 로직 - 구간 분할하여 해당 구간의 최대 넓이 구하기

시뮬레이션

∙ 4번 로직 - 각 구간의 넓이를 비교하여 최대 넓이 구하기

코드 설명

✔︎ 1번 로직 코드 - 세그먼트 트리 생성

✔︎ 2~4번 로직 코드 - 구간 분할하여 해당 구간의 최대 넓이 구해서 비교하기

풀이 코드

'Dot Algo∙ DS > PS' 카테고리의 다른 글

티스토리툴바

티스토리툴바

[BOJ] 백준 6549번 히스토그램에서 가장 큰 직사각형 (Java)

#6549 히스토그램에서 가장 큰 직사각형

▸ 문제

▸ 입력

▸ 출력

문제 풀이

구상

스케치

∙ 1번 로직 - 세그먼트 트리 생성

∙ 2번 로직 - 구간 분할하여 해당 구간의 최대 넓이 구하기

시뮬레이션

∙ 4번 로직 - 각 구간의 넓이를 비교하여 최대 넓이 구하기

코드 설명

✔︎ 1번 로직 코드 - 세그먼트 트리 생성

✔︎ 2~4번 로직 코드 - 구간 분할하여 해당 구간의 최대 넓이 구해서 비교하기

풀이 코드

'Dot Algo∙ DS > PS' 카테고리의 다른 글

'Dot Algo∙ DS/PS' 관련글

티스토리툴바

티스토리툴바