BOJ 백준 2357 : 최솟값과 최댓값

시작하면서

　이번 문제는 Segment Tree 문제이다.

BOJ 2357 - 최솟값과 최댓값

​

문제 이해

​ 해당 문제는 약 10만개의 데이터를 범위를 나누어서 최대 10만번 반복해야하기 때문에 무작정 전부 계산하면 시간초과가 발생한다. 원래는 Interval Tree로 문제를 해결하려고 했으나 구현에 관한 자료가 부족해서 세그먼트트리로 해결하고자 한다.

1. 각 범위에 따른 최소, 최대값을 세그먼트 트리에 저장한다.
2. 범위를 인풋으로 받으면, 해당 범위 내에서 탐색을 통해 최소, 최대값을 찾아 출력한다.

​

해결

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

pair<int, int> InitTree(vector<pair<int, int>>& tree, const vector<int>& number, int start, int end, int currentIndex)
{
	if (start == end)
	{
		tree[currentIndex].first = number[start];
		tree[currentIndex].second = number[start];

		return tree[currentIndex];
	}

	int mid = (int)((start + end) * 0.5f);

	pair<int, int> a = InitTree(tree, number, start, mid, currentIndex * 2);
	pair<int, int> b = InitTree(tree, number, mid + 1, end, currentIndex * 2 + 1);

	tree[currentIndex].first = (a.first < b.first) ? a.first : b.first;
	tree[currentIndex].second = (a.second > b.second) ? a.second : b.second;

	return tree[currentIndex];
}

pair<int, int> GetMinMaxElement(const vector<pair<int, int>>& tree, int currentIndex, int start, int end, int left, int right)
{
	// 범위가 겹치지 않는 경우
	if (start > right || end < left)
		return make_pair(INT_MAX, 0);
	
	// 구하려는 범위가 완전히 겹쳐있는 경우
	if (left <= start && end <= right)
		return tree[currentIndex];

	int mid = (int)(start + end) * 0.5f;
	pair<int, int> l, r;

	l = GetMinMaxElement(tree, currentIndex * 2, start, mid, left, right);
	r = GetMinMaxElement(tree, currentIndex * 2 + 1, mid + 1, end, left, right);

	int min = (l.first < r.first) ? l.first : r.first;
	int max = (l.second > r.second) ? l.second : r.second;

	return make_pair(min, max);
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	// pair<min, max>
	vector<pair<int, int>> tree;
	vector<int> number;
	int N, M;

	cin >> N >> M;

	tree.resize(N * 4);
	number.resize(N + 1);
	for (int i = 1; i <= N; i++)
	{
		cin >> number[i];
	}

	InitTree(tree, number, 1, N, 1);

	for (int i = 0; i < M; i++)
	{
		int left, right;

		cin >> left >> right;

		pair<int, int> minmax = GetMinMaxElement(tree, 1, 1, N, left, right);

		cout << minmax.first << " " << minmax.second << "\n";
	}

	return 0;
}

​

마치며

　스터디에서는 Interval Tree를 주제로 공부 및 구현을 하고 문제를 해결하려고 했으나… 일부 구현을 했지만 문제를 풀기에는 검증할 수 있는 자료가 부족해서 아쉽지만 세그먼트 트리로 푸는 것으로 만족했다. 세그먼트 트리는 많이 안 해봐서 그런지 50% 문제도 여러 시도를 해서야 겨우 해결했다. 숙련을 위해 다양한 문제를 풀어봐야겠다.