[백준] 2357번 : 최솟값과 최댓값

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 수열의 특정 구간 내의 최솟값과 최댓값을 구하는 문제로, 세그먼트 트리 알고리즘을 사용하여 풀이했다.

1) 수열을 저장할 datas, 최솟값 트리를 저장할 minTree 배열, 최댓값 트리를 저장할 maxTree 배열을 선언한다. 이 때 트리들의 크기는 수열 배열의 최대 크기의 4배 이상으로 설정한다.

2) 수의 개수 n과 최솟값 및 최댓값을 구해야하는 범위의 개수 m을 입력 받아 저장하고, n개의 수를 입력받아 datas에 저장한다.

3) minInit(), maxInit() 함수를 통해 최솟값 트리와 최댓값 트리를 초기화 한다.

• 최상위 노드부터 시작해 데이터 범위를 반씩 분할하여 구간곱을 저장하는 방식으로 트리를 채운다. 재귀를 통해 가장 작은 범위의 값을 구해, 그 값들로 더 큰 범위의 값을 구한다.
• 최솟값 트리의 경우
  • 현재 순서 노드의 값 = 왼쪽 자식 노드의 값과 오른쪽 자식 노드의 값 중 더 작은 값
• 최댓값 트리의 경우
  • 현재 순서 노드의 값 = 왼쪽 자식 노드의 값과 오른쪽 자식 노드의 값 중 더 큰 값
• 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때) 해당 수를 현재 순서 노드의 값으로 설정하고 반환한다.

4) m번의 최솟값 및 최댓값 출력을 실행한다.

• 항상 a < b임이 보장되지 않기 때문에 a < b일 때와 아닐 때의 조건을 나눈다.
• findMin()과 findMax() 함수를 통해 현재 순서에서 구해야하는 범위의 최솟값 및 최댓값을 구한다.
• 최솟값 트리의 경우
  • 범위 밖에 있는 경우 INF(수열의 수로 올 수 없는 큰 값)을 반환한다.
  • 범위 안에 있는 경우 현재 순서 노드의 최솟값을 반환한다.
  • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 각 범위에 대해 findMin()을 실행한다.
• 최댓값 트리의 경우
  • 범위 밖에 있는 경우 0을 반환한다.
  • 범위 안에 있는 경우 현재 순서 노드의 최댓값을 반환한다.
  • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 각 범위에 대해 findMax()을 실행한다.

🖥️ 풀이 코드

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

int n, m;
long long minTree[400004];
long long maxTree[400004];
long long datas[100001];
const long long INF = 1000000001;

long long minInit(int start, int end, int node)
{
	if (start == end) return minTree[node] = datas[start];
	int mid = start + (end - start) / 2;
	return minTree[node] = min(minInit(start, mid, node * 2), minInit(mid + 1, end, node * 2 + 1));
}

long long findMin(int start, int end, int node, int left, int right)
{
	if (end < left || right < start) return INF;
	if (left <= start && end <= right) return minTree[node];
	int mid = start + (end - start) / 2;
	return min(findMin(start, mid, node * 2, left, right), 
		findMin(mid + 1, end, node * 2 + 1, left, right));
}

long long maxInit(int start, int end, int node)
{
	if (start == end) return maxTree[node] = datas[start];
	int mid = start + (end - start) / 2;
	return maxTree[node] = max(maxInit(start, mid, node * 2), maxInit(mid + 1, end, node * 2 + 1));
}

long long findMax(int start, int end, int node, int left, int right)
{
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return maxTree[node];
	int mid = start + (end - start) / 2;
	return max(findMax(start, mid, node * 2, left, right),
		findMax(mid + 1, end, node * 2 + 1, left, right));
}

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> datas[i];
	
	minInit(1, n, 1);
	maxInit(1, n, 1);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		if (a < b)
		{
			cout << findMin(1, n, 1, a, b) << ' ';
			cout << findMax(1, n, 1, a, b) << '\n';
		}
		else
		{
			cout << findMin(1, n, 1, b, a) << ' ';
			cout << findMax(1, n, 1, b, a) << '\n';
		}	
	}
}