[G1] 백준 6213번 Balanced Lineup C++ 세그먼트 트리

리뷰

 

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

구간 최대값 - 최소값을 출력하는 문제, 다국어 문제라 영문으로 되어있다. 지문이 짧아 이해하긴 쉬웠다.

 

 

전역 변수

• N : n의 최대값을 정의하기 위한 정수형 상수 변수
• n : 소의 개수를 저장하기 위한 변수
• q : 쿼리의 개수를 저장하기 위한 변수
• nodes : 소의 높이를 저장하기 위한 정수형 배열
• Mintree : 소의 높이 기준으로 구간 최소값을 저장하기 위한 세그먼트 트리
• Maxtree : 소의 높이 기준으로 구간 최대값을 저장하기 위한 세그먼트 트리
• MM : 쿼리문 탐색 시 최소 및 최대값을 저장하기 위해 필요한 변수를 정의한 구조체

 

함수

1. build

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

 

세그먼트 트리 초기 상태를 초기화 하기 위한 함수

1. 매개변수로 세그먼트 트리의 인덱스가 될 node와 배열의 구간 s, e를 전달 받는다.
2. 기저 조건으로 s와 e가 같을 경우 리프노드에 도달했으므로 각 트리의 노드에 배열의 값을 저장해 준다.
3. 리프노드가 아닌 경우 좌우로 리프노드 까지 재귀를 통해 배열의 값을 리프 노드에 저장해 준다.
4. 재귀를 빠져나오면 좌우 두 노드를 비교해 상위 노드에 최소 혹은 최대값을 저장해 준다.

 

2. query

MM query(int node, int s, int e, int L, int R)

 

구간의 최소 및 최대값을 찾아 구조체 MM타입으로 리턴하기 위한 함수

1. 매개변수로 세그먼트 트리의 node와 현재 탐색 범위 s, e, 찾고자 하는 범위 L, R을 전달받는다.
2. 만약 찾고자 하는 범위가 현재 탐색 범위를 벗어난 경우 100만 이상의 값과 0을 리턴해 준다.
3. 현재 탐색 범위가 찾고자 하는 범위 내에 있다면 각 세그먼트 트리의 현재 노드값을 리턴해 준다.
4. 이후 노드로 좌우 재귀를 통해 왼쪽 재귀의 값은 left, 오른쪽 재귀의 값은 right로 받아준다.
5. left, right의 minv 중 작은값과, left, right의 maxv 중 큰 값을 묶어 리턴해 준다.

 

문제풀이

1. n, q값을 입력 받고, n개의 인자를 nodes배열에 입력 받아준다.
2. build 함수를 통해 nodes배열을 기준으로 Mintree, Maxtree를 초기화 해준다.
3. q개의 쿼리 정보를 입력 받아 각 쿼리에서 요구하는 구간을 s, e에 입력 받아준다.
4. query함수를 통해 s부터 e까지의 구간 중 최소 및 최대값을 MM타입의 변수 result에 받아준다.
5. result의 maxv에서 minv을 뺀 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• Mintree, Maxtree 모두 같은 배열을 쓰므로 build와 query 함수를 따로 둘 필요는 없다.
• 문제 풀이에 0-based-index를 사용했으므로 각 쿼리에서 입력 받은 구간은 -1처리 해주어야 한다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 50000;
int n, q;
int nodes[N];
int Mintree[N * 4];
int Maxtree[N * 4];
struct MM {
	int minv, maxv;
};

void build(int node, int s, int e) {
	if (s == e) {
		Mintree[node] = nodes[s];
		Maxtree[node] = nodes[s];
		return;
	}
	int mid = (s + e) / 2;
	build(node * 2, s, mid);
	build(node * 2 + 1, mid + 1, e);
	Mintree[node] = min(Mintree[node * 2], Mintree[node * 2 + 1]);
	Maxtree[node] = max(Maxtree[node * 2], Maxtree[node * 2 + 1]);
}

MM query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return { 1000001, 0 };
	if (L <= s && e <= R) return { Mintree[node], Maxtree[node] };
	int mid = (s + e) / 2;
	MM left = query(node * 2, s, mid, L, R);
	MM right = query(node * 2 + 1, mid + 1, e, L, R);
	return { min(left.minv, right.minv), max(left.maxv, right.maxv) };
}

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

	cin >> n >> q;
	for (int i = 0; i < n; ++i) cin >> nodes[i];

	build(1, 0, n - 1);

	while (q--) {
		int s, e; cin >> s >> e;
		MM result = query(1, 0, n - 1, s - 1, e - 1);
		cout << result.maxv - result.minv << "\n";
	}
}