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

 

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

 

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

 

2357번: 최솟값과 최댓값

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

www.acmicpc.net

---

 

해결전략

 

세크먼트 트리 Segment Tree

자료 구조

 

---

 

정답코드

 

#include <iostream>
#include <vector>
#include <cmath> // ceil, log2, min, max에 필요
using namespace std;
 
#define INF 1000000001
 
struct Value{
	long long minNum, maxNum;
};
 
int n, m;
vector<int> v;
vector<Value> sTree;
 
Value SegmentTree(int node, int start, int end)
{
	if (start == end) { // node가 leaf node인 경우
		sTree[node].minNum = v[start];
		sTree[node].maxNum = v[start];
		return sTree[node];
	}
 
	int mid = (start + end) / 2;
 
	Value left = SegmentTree(node * 2, start, mid);
	Value right = SegmentTree(node * 2 + 1, mid + 1, end);
 
	sTree[node].minNum = min(left.minNum, right.minNum);
	sTree[node].maxNum = max(left.maxNum, right.maxNum);
 
	return sTree[node];
}
 
Value FindMinMax(int node, int start, int end, int left, int right)
{
	if (left > end || right < start) {
		return Value{ INF, 0 };
	}
 
	if (left <= start && end <= right){
		return sTree[node];
	}
 
	int mid = (start + end) / 2;
 
	Value tempLeft = FindMinMax(node * 2, start, mid, left, right);
	Value tempRight = FindMinMax(node * 2 + 1, mid + 1, end, left, right);
 
	Value result;
	result.minNum = min(tempLeft.minNum, tempRight.minNum);
	result.maxNum = max(tempLeft.maxNum, tempRight.maxNum);
 
	return result;
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n >> m;
	v.resize(n);
	for(int i = 0; i < n; i++){
		cin >> v[i];
	}
 
	int treeHeight = (int)ceil(log2(n));
	int treeSize = (1 << (treeHeight + 1));
	sTree.resize(treeSize);
 
	SegmentTree(1, 0, n - 1);
	
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
 
		Value tmp = FindMinMax(1, 0, n - 1, a-1, b-1);
		cout << tmp.minNum << " " << tmp.maxNum << "\n";
	}
 
	return 0;
}

 

 

 

주석

#include <iostream> 
#include <vector>   
#include <cmath>    // ceil, log2, min, max에 사용
using namespace std;
 
#define INF 1000000001
 
struct Value{  // 세그먼트 트리의 각 노드에 저장될 구조체
	long long minNum, maxNum;
};
 
int n, m;  				// n은 입력값의 개수, m은 쿼리의 개수
vector<int> v;  		// 입력값을 저장할 벡터
vector<Value> sTree; 	// 세그먼트 트리
 
// 세그먼트 트리를 구성하는 함수. 재귀적으로 호출되며, 각 노드에는 해당 범위의 최소값과 최대값이 저장됨.
Value SegmentTree(int node, int start, int end)
{	
	if (start == end) { // node가 leaf node인 경우
		sTree[node].minNum = v[start];
		sTree[node].maxNum = v[start];
		return sTree[node];
	}
 
	int mid = (start + end) / 2;
 
	Value left = SegmentTree(node * 2, start, mid);  		// 왼쪽 자식 노드를 구성
	Value right = SegmentTree(node * 2 + 1, mid + 1, end);  // 오른쪽 자식 노드를 구성
 
	sTree[node].minNum = min(left.minNum, right.minNum);  // 왼쪽 자식 노드와 오른쪽 자식 노드의 최소값 중 작은 값을 저장
	sTree[node].maxNum = max(left.maxNum, right.maxNum);  // 왼쪽 자식 노드와 오른쪽 자식 노드의 최대값 중 큰 값을 저장
 
	return sTree[node];
}
 
// 주어진 범위 [left, right]에서 최소값과 최대값을 찾는 함수.
Value FindMinMax(int node, int start, int end, int left, int right)
{
	if (left > end || right < start) {
		return Value{ INF, 0 };  // 범위 밖인 경우, minNum은 INF, maxNum은 0으로 설정
	}
 
	if (left <= start && end <= right){
		return sTree[node];  // 범위 안에 전체가 포함되는 경우, 해당 노드의 값을 반환
	}
 
	int mid = (start + end) / 2;
 
	Value tempLeft = FindMinMax(node * 2, start, mid, left, right);  		// 왼쪽 자식 노드에서 찾기
	Value tempRight = FindMinMax(node * 2 + 1, mid + 1, end, left, right);  // 오른쪽 자식 노드에서 찾기
 
	Value result;
	result.minNum = min(tempLeft.minNum, tempRight.minNum); // 왼쪽과 오른쪽에서 찾은 최소값 중 작은 값을 저장
	result.maxNum = max(tempLeft.maxNum, tempRight.maxNum); // 왼쪽과 오른쪽에서 찾은 최대값 중 큰 값을 저장
 
	return result;
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n >> m; 
	v.resize(n);  
	for(int i = 0; i < n; i++){
		cin >> v[i]; 
	}
 
	int treeHeight = (int)ceil(log2(n));  	// 세그먼트 트리의 높이 계산
	int treeSize = (1 << (treeHeight + 1)); // 세그먼트 트리의 크기 계산
	sTree.resize(treeSize);  				// 세그먼트 트리의 크기를 설정
 
	SegmentTree(1, 0, n - 1);  // 세그먼트 트리 구성
	
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;  // 쿼리 범위
 
		Value tmp = FindMinMax(1, 0, n - 1, a-1, b-1);  // 쿼리 범위에서 최소값과 최대값을 찾음
		cout << tmp.minNum << " " << tmp.maxNum << "\n"; 
	}
 
	return 0;
}

 

 

---