[백준 C++] 2357 최솟값과 최댓값

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

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

풀이

일반적인 브루트포스방법으로 매번 구간마다 순회하며 최소최대를찾으면 당연히 시간오바가된다.
빈번하게 구간을 나누어 탐색을 해야하는경우 또한 세그먼트트리를 이용하면 해결가능하다.
여기서는 최솟값,최댓값을 찾아야하므로, 2개의 세그먼트트리를 구현하여 풀었다.
이때 트리의 리프노드의 갯수는 배열의 원소갯수이므로
그 높이는 log(N)+1을 반올림하여 구하여, 트리의 크기를 정하였다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

//최소, 최대트리를 각각 구현하는 함수
void makeTree(vector<int> &arr, vector<int>& minTree, vector<int>& maxTree, 
	int node, int start, int end) {
	if (start == end) { //리프노드 일때 그대로 저장
		minTree[node] = maxTree[node] = arr[start];
	}
	else {
		makeTree(arr, minTree, maxTree, node * 2, start, (start + end) / 2);
		makeTree(arr, minTree, maxTree, node * 2 + 1, (start + end) / 2 + 1, end);
		//node는 현재 주목하는 노드의 인덱스이며, 그 왼쪽자식 오른쪽자식중
		//최솟값, 최댓값으로 현재노드의 값을 갱신해준다.
		//리프노드의 부모노드부터 쌓아올려지는 방식이다.
		//호출은 top-down임
		minTree[node] = min(minTree[node * 2], minTree[node * 2 + 1]);
		maxTree[node] = max(maxTree[node * 2], maxTree[node * 2 + 1]);
	}
}

//a, b범위에따른 최소, 최댓값을 쌍으로 묶어서 리턴하는 함수
//최솟값, 최댓값쌍을 리턴
//start, end 는 가능한 최대범위
//left, right 는 찾고자하는 구간
pair<int, int> findMinMax(vector<int> &minTree, vector<int> &maxTree, 
	int node, int start, int end, int left, int right) {
	if (left > end || right < start) { //구간이 잘못된경우
		//최솟값으로 최대를, 최댓값으로 최소를 리턴
		return make_pair(INT32_MAX, 0);
	}
	else if (left <= start && end <= right) {
		return make_pair(minTree[node], maxTree[node]);
	}
	else {
		pair<int, int> L, R;
		L = findMinMax(minTree, maxTree, node * 2, start, (start + end) / 2, left, right);
		R = findMinMax(minTree, maxTree, node * 2 + 1, (start + end) / 2 + 1, end, left, right);
		return make_pair(min(L.first, R.first), max(L.second, R.second));
	}
}

int main(void) {
	int N, M;
	scanf("%d%d", &N, &M);
	vector<int> arr(N);
	int h = (int)ceil(log2(N))+1;
	vector<int> minTree(pow(2, h)), maxTree(pow(2, h));
	for (int i = 0, temp; i < N; i++) {
		scanf("%d", &temp);
		arr[i] = temp;
	}
	makeTree(arr, minTree, maxTree, 1, 0, N-1);
	while (M--) {
		int a, b;
		scanf("%d%d", &a, &b);
		pair<int, int> res = findMinMax(minTree, maxTree, 1, 0, N-1, a-1, b-1);
		printf("%d %d\n", res.first, res.second);
	}

	return 0;
}

핵심인 findMinMax함수에서, 노드를기준으로 왼쪽자식노드, 오른쪽자식노드를 재귀호출하여 가능한 모든 하위 노드에서 최솟값, 최댓값을 구하여 리턴하도록 하는것이 포인트이다! 심지어 이 함수의 인자또한 기존의 세그먼트트리의 구간합을구하는 sum함수와 일치한다.