[P5] 백준 1725번 히스토그램 C++ 세그먼트 트리

리뷰

 

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

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 문제

세그먼트 트리를 활용해 히스토그램의 각 높이를 비교하고 구간에서 가장 작은 높이의 인덱스를 관리해 준다.

query를 수행하며 각 구간에서의 가장 작은 높이를 가진 막대 기준으로 만들 수 있는 사각형의 최대 넓이를 구한다.

 

 

전역 변수

• n : 주어지는 히스토그램의 개수
• MAX_N : n이 입력될 수 있는 최대의 수, 10만으로 저장했다.
• nodes : 히스토그램의 정보를 저장할 정수형 배열, 크기는 MAX_N으로 초기화 한다.
• tree : 세그먼트 트리 정보를 저장할 정수형 배열, 크기는 MAX_N * 4로 초기화 한다.

 

함수

1. build

void build(int node, int s, int e)

 

nodes배열을 사용하여 세그먼트 트리를 초기화 하는 함수

1. 매개변수로 세그먼트 트리의 노드 인덱스, 배열 구간의 시작 인덱스 s, 배열 구간의 종료 인덱스e를 받는다.
2. 만약 s == e인 경우라면 리프 노드인 경우이다, 현재 노드에 배열의 인덱스 s값을 저장한다. (e도 상관 없음)
3. 리프노드가 아닐 경우 s + e / 2를 통해 mid인덱스를 구해준다.
4. 현재 노드에서 좌우로 나뉘어 build함수를 호출해 재귀를 진행한다.
5. 현재 노드는 좌우 자식 노드의 높이를 비교하여 더 작은 값을 가진 배열의 인덱스로 초기화 해준다.

 

2. getIndex

int getIndex(int node, int s, int e, int L, int R)

 

배열의 L ~ R구간에서 가장 작은 높이를 가진 히스토그램의 인덱스를 리턴하는 함수

1. 만약 탐색 범위를 벗어난 경우 -1을 리턴해 준다.
2. 세그먼트 트리의 탐색 범위가 배열의 구간을 포함하는 경우 tree[node]를 리턴해 준다.
3. 위 기저조건에 해당하지 않는다면 mid를 s + e / 2로 초기화 한다.
4. left, right변수에 각각 좌, 우 자식 노드에 재귀를 진행하고 나온 값을 저장해 준다.
5. 만약 left가 -1일 경우 right를 리턴해 준다, 반대로 right가 -1일 경우 left를 리턴해 준다.
6. 둘 다 -1이 아닐 경우 nodes배열 상에서 더 낮은 값을 가진 인덱스를 리턴해 준다.

 

3. query

int query(int s, int e)

 

s ~ e범위에서의 가장 낮은 높이의 인덱스를 찾고, 구간을 곱해 사각형의 넓이를 구하는 함수

1. 만약 s가 e보다 크다면 0을 리턴해 준다.
2. min_index를 getIndex에 s, e를 매개변수로 전달하여 현재 구간에서의 가장 높이가 낮은 히스토그램의 인덱스를 찾는다.
3. all 변수에 현재 구간 * min_index높이를 갖는 사각형의 넓이를 저장해 준다.
4. left, right변수에 각각 s ~ min_index - 1, min_index + 1, e까지를 재귀탐색을 하며 값을 저장해 준다.
5. all, left, right중에서 가장 큰 값을 출력해 준다.

 

문제풀이

1. n값을 입력 받고, nodes배열에 n개의 히스토그램 높이를 초기화 해준다.
2. build 함수를 통해 세그먼트 트리를 초기화 해준다.
3. query함수를 0 ~ n - 1범위로 수행하고 리턴받은 값을 출력해 준다.

 

참고 사항

모든 구간에서의 최소값을 구하기 위해선 세그먼트 트리를 히스토그램의 인덱스로 관리해 주어야 한다.

 

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

int n;
const int MAX_N = 100000;
int nodes[MAX_N];
int tree[MAX_N * 4];

void build(int node, int s, int e) {
	if (s == e) tree[node] = s;
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		tree[node] = nodes[tree[node * 2]] <= nodes[tree[node * 2 + 1]] ? tree[node * 2] : tree[node * 2 + 1];
	}
}

int getIndex(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return -1;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	int left = getIndex(node * 2, s, mid, L, R);
	int right = getIndex(node * 2 + 1, mid + 1, e, L, R);

	if (left == -1) return right;
	if (right == -1) return left;
	return nodes[left] <= nodes[right] ? left : right;
}

int query(int s, int e) {
	if (s > e) return 0;
	int min_index = getIndex(1, 0, n - 1, s, e);
	int all = nodes[min_index] * (e - s + 1);
	int left = query(s, min_index - 1);
	int right = query(min_index + 1, e);
	return max({ all, left, right });
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> nodes[i];
	build(1, 0, n - 1);
	cout << query(0, n - 1);
}