[BOJ] 6549. 히스토그램에서 가장 큰 사각형 (세그먼트 트리)

🔗 문제

https://www.acmicpc.net/problem/6549

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

 

💻 풀이 및 코드

문제 유형 : 분할정복, 세그먼트 트리

 

히스토그램에서 가장 큰 사각형의 넓이를 찾아 출력하는 문제

(히스토그램: 직사각형 여러 개가 아래쪽에 정렬되어 있는 도형)

 

풀이

이 문제는 풀 수 있는 방법이 여러 가지가 있다.

 

1. 분할 정복

2. 분할 정복 + 세그먼트 트리

3. 스택

 

나는 1번으로 풀다가 시간 초과가 나서 2번으로 풀었다.

 

먼저, 분할 정복을 이 문제에서 어떻게 활용할 지 알아보자.

https://www.acmicpc.net/blog/view/12

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

 

백준님께서 정리를 아주 잘해놓으셔서 도움이 많이 됐다.

요약하면,

• 가장 높이가 낮은 사각형을 찾는다.
• ( 찾은 가장 낮은 사각형의 높이 x 사각형들의 갯수 ) 를 하면 현재 구할 수 있는 가장 넓은 사각형의 넓이가 구해진다.
• 가장 높이가 낮은 사각형을 기준으로 왼쪽, 오른쪽 구간을 탐색한다.

• 위에서 진행했던 순서를 반복한다. 마찬가지로 구간 내 가장 낮은 사각형의 높이를 찾아 구간에 속한 사각형의 갯수만큼 곱해 넓이를 구하고 다시 왼쪽 오른쪽 구간을 탐색한다.

여기서 가장 낮은 사각형의 높이를 구할 때 하나씩 비교하면 O(N) 의 시간 복잡도가 걸린다.

세그먼트 트리를 사용해 O(logN) 으로 줄일 수 있다.

 

세그먼트 트리에 대해 알아보자.

https://book.acmicpc.net/ds/segment-tree

세그먼트 트리

여기서 아주 정리를 잘 해놓으셨다.

결론만 요약하면,

• 세그먼트 트리는 구간 합을 저장한다.
• 이 문제에선 구간 내에 가장 높이가 낮은 사각형의 인덱스를 저장한다.
• 세그먼트 트리는 Full Binary Tree 구조이다. (N(:사각형의 갯수) 가 2 의 제곱이라면 Full Binary Tree)
• 이 때 트리의 높이(h) 는 logN 이다
• 트리의 속한 노드의 갯수는 2^(h+1) -1 이다
• 분할 정복을 사용해 트리를 초기화한다. 

관련 코드

public class Main_prac {
	public static void main(String[] args) throws Exception {
    
    	...
        // 갯수가 N 인 트리의 높이 = logN
        int H = (int)Math.ceil(Math.log10(N)/Math.log10(2));

        // 높이가 H 인 Full binary Tree 의 노드의 갯수 = 2^(H+1)-1 (인덱스를 1부터 사용하기 때문에 -1 생략)
        int tree_size = 1 << H+1;

        int[] tree = new int[tree_size];
        
        init(tree, heights, 1, 0, N-1);		// 트리 초기화
	}
	
	static void init(int[] tree, int[] heights, int node, int start, int end) {
		if(start == end) {
			tree[node] = start;
			return;
		}
		
		init(tree, heights, node*2, start, (start+end)/2);
		init(tree, heights, node*2+1, (start+end)/2+1, end);
		if(heights[tree[node*2]] < heights[tree[node*2+1]]) {
			tree[node] = tree[node*2];
		} else {
			tree[node] = tree[node*2+1];
		}
	}
	

}

 

전체 코드

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


/* 분할 정복 + 세그먼트 트리
 * 
 * 1. 현재 범위 안에 가장 높이가 작은 사각형을 찾는다.
 * 1-1. 세그먼트 트리를 사용해 찾는다. 세그먼트 트리에는 범위 내에 가장 작은 높이의 사각형의 index 가 저장되어 있다.
 *      (기존의 세그먼트 트리에는 구간합을 저장했었다.)
 * 2. 넓이를 계산한다. 넓이 = 범위 안에 포함된 사각형들의 갯수 x 가장 낮은 높이
 * 3. 가장 낮은 높이의 사각형을 기준으로 왼쪽, 오른쪽으로 탐색한다.
 * 
 */
public class Main_prac {
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_6549.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		while(true) {
			st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			if(N==0) break;
			
			int[] heights = new int[N];
			for(int i=0; i<N; i++) {
				heights[i] = Integer.parseInt(st.nextToken());
			}
			
			// 갯수가 N 인 트리의 높이 = logN
			int H = (int)Math.ceil(Math.log10(N)/Math.log10(2));
			
			// 높이가 H 인 Full binary Tree 의 노드의 갯수 = 2^(H+1)-1 (인덱스를 1부터 사용하기 때문에 -1 생략)
			int tree_size = 1 << H+1;
			
			int[] tree = new int[tree_size];
			init(tree, heights, 1, 0, N-1);		// 트리 초기화
			
			// 범위 내 사각형 크기 계산
			sb.append(getArea(tree, heights, N, 0, N-1)).append("\n");
		}
		System.out.println(sb.toString());
		br.close();
	}
	
	static long getArea(int[] tree, int[] heights, int N, int start, int end) {
		int idx = findSmallSquare(tree, heights, 1, 0, N-1, start, end);		// 구간 내 가장 작은 사각형의 위치 return
		// 넓이 계산
		long area = (long)(end-start+1) * (long)heights[idx];
		
		// 왼쪽 탐색
		if(start < idx) {
			long area1 = getArea(tree, heights, N, start, idx-1);
			if(area < area1)
				area = area1;
		}
		// 오른쪽 탐색
		if(idx < end) {
			long area2 = getArea(tree, heights, N, idx+1, end);
			if(area < area2)
				area = area2;
		}
		
		return area;
	}
	
	// start~end : 탐색 범위, i~j: 찾고자 하는 범위
	static int findSmallSquare(int[] tree, int[] heights, int node, int start, int end, int i, int j) {
		if(end < i || j < start) return -1;		// 탐색 범위 벗어남
		if(i <= start && end <= j) {			// 탐색 범위 안에 속함
			return tree[node];
		}
		
		// 왼쪽 탐색
		int m1 = findSmallSquare(tree, heights, node*2, start, (start+end)/2, i, j);
		// 오른쪽 탐색
		int m2 = findSmallSquare(tree, heights, node*2+1, (start+end)/2+1, end, i, j);
		
		if(m1 == -1) return m2;
		if(m2 == -1) return m1;
		
		if(heights[m1] < heights[m2]) return m1;
		else return m2; 
	}
	
	
	
	static void init(int[] tree, int[] heights, int node, int start, int end) {
		if(start == end) {
			tree[node] = start;
			return;
		}
		
		init(tree, heights, node*2, start, (start+end)/2);
		init(tree, heights, node*2+1, (start+end)/2+1, end);
		if(heights[tree[node*2]] < heights[tree[node*2+1]]) {
			tree[node] = tree[node*2];
		} else {
			tree[node] = tree[node*2+1];
		}
	}
	

}

---

Reference

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

 

세그먼트 트리