[Baekjoon] 2357번: 최솟값과 최댓값 (Gold) - C++ 풀이

세그먼트트리 자료 구조

문제

문제 링크

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에 대한 답을 최솟값, 최댓값 순서로 출력한다.

문제 조건

• 목표: N개의 정수 데이터가 주어질 때, 특정 구간 [a, b] 내에서 최솟값과 최댓값을 찾는 M개의 쿼리를 효율적으로 처리한다.

• 입력 상태: N과 M은 최대 100,000이며, 각 정수는 1부터 1,000,000,000 사이의 값을 갖는다.

• 핵심 조건: 매번 구간을 탐색하면 O(N*M)으로 시간 초과가 발생하므로, 트리 구조를 이용해 구간 합이나 최댓값/최솟값을 O(log N)에 처리할 수 있는 세그먼트 트리를 사용해야 한다.

---

풀이

핵심 알고리즘

세그먼트 트리

• 시간 복잡도: O(N + M log N) — 트리 구축에 O(N), M번의 쿼리 처리에 각각 O(log N)이 소요되어 약 124ms 내외로 처리 가능하다.

핵심 아이디어

세그먼트 트리를 구성하여 각 노드에 해당 구간의 최솟값과 최댓값을 동시에 저장한다. 초기화 과정에서 입력값을 리프 노드에 저장하고 부모 노드로 올라가며 최솟값과 최댓값을 갱신한 뒤, 쿼리가 들어올 때마다 구간에 걸치는 노드들만 선택하여 결과를 도출한다.

① 세그먼트 트리 구조 정의 및 메모리 할당

각 노드가 최솟값(minV)과 최댓값(maxV)을 모두 관리할 수 있도록 구조체를 정의한다. 배열 크기를 4,000,001로 설정했는데, 이는 N=100,000일 때 필요한 4N보다 10배나 큰 크기로, 메모리 제한(64MB)에 거의 근접하게 사용되는 특이점이 있다.

struct dict {
	long long minV, maxV;
};

dict arr[4'000'001];

② 트리 초기화 (Build)

재귀적으로 트리를 내려가며 리프 노드(left == right)에서 직접 입력을 받아 저장한다. 이후 자식 노드들이 반환한 최솟값과 최댓값을 비교하여 현재 부모 노드의 범위를 갱신함으로써 쿼리 시 빠르게 참조할 수 있는 기반을 마련한다.

void init(int index, int left, int right) {
	if (left == right) {
		cin >> arr[index].minV;
		arr[index].maxV = arr[index].minV;
		return;
	}
	int mid = left + (right - left) / 2;

	init(index * 2, left, mid);
	init(index * 2 + 1, mid + 1, right);

	arr[index].minV = min(arr[index * 2].minV, arr[index * 2 + 1].minV);
	arr[index].maxV = max(arr[index * 2].maxV, arr[index * 2 + 1].maxV);
}

③ 구간 최솟값/최댓값 쿼리

찾고자 하는 범위 [st, ed]와 현재 노드의 범위 [left, right]를 비교한다. 범위를 완전히 벗어나면 항등원(최솟값은 LLONG_MAX, 최댓값은 LLONG_MIN)을 반환하고, 범위에 완전히 포함되면 미리 계산된 노드 값을 반환하여 연산을 최적화한다.

ll rangeMin(int index, int left, int right, int st, int ed) {
	if (ed < left || right < st)
		return LLONG_MAX;

	if ((left == right) || (st <= left && right <= ed)) {
		return arr[index].minV;
	}

	int mid = left + (right - left) / 2;

	ll leftN = rangeMin(index * 2, left, mid, st, ed);
	ll rightN = rangeMin(index * 2 + 1, mid + 1, right, st, ed);
	return min(leftN, rightN);
}

④ 메인 로직 및 입출력 최적화

트리를 1회 구축한 뒤 M번의 쿼리를 수행한다. 쿼리 결과인 minVal과 maxVal을 공백으로 구분하여 출력하며, 대량의 입출력을 빠르게 처리하기 위해 ios_base::sync_with_stdio(false)를 사용한다.

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("sample_input.txt","r",stdin);
	int a, b;

	cin >> N >> M;
	init(1, 1, N);
	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		minVal = rangeMin(1, 1, N, a, b);
		maxVal = rangeMax(1, 1, N, a, b);
		cout << minVal << " " << maxVal << "\n";
	}
}

---

성능

• 메모리 : 64520 KB

• 시간 : 124 ms

코드 (C++)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<climits>

using namespace std;
#define ll long long

struct dict {
	long long minV, maxV;
};

dict arr[4'000'001];

int N, M;
ll inC;

ll minVal = LLONG_MAX;
ll maxVal = LLONG_MIN;

void init(int index, int left, int right) {
	if (left == right) {
		cin >> arr[index].minV;
		arr[index].maxV = arr[index].minV;
		return;
	}
	int mid = left + (right - left) / 2;

	init(index * 2, left, mid);
	init(index * 2 + 1, mid + 1, right);

	arr[index].minV = min(arr[index * 2].minV, arr[index * 2 + 1].minV);
	arr[index].maxV = max(arr[index * 2].maxV, arr[index * 2 + 1].maxV);
}

ll rangeMin(int index, int left, int right, int st, int ed) {
	if (ed < left || right < st)
		return LLONG_MAX;

	if ((left == right) || (st <= left && right <= ed)) {
		return arr[index].minV;
	}

	int mid = left + (right - left) / 2;

	ll leftN = rangeMin(index * 2, left, mid, st, ed);
	ll rightN = rangeMin(index * 2 + 1, mid + 1, right, st, ed);
	return min(leftN, rightN);
}
ll rangeMax(int index, int left, int right, int st, int ed) {
	if (ed < left || right < st)
		return LLONG_MIN;

	if ((left == right) || (st <= left && right <= ed)) {
		return arr[index].maxV;
	}

	int mid = left + (right - left) / 2;

	ll leftN = rangeMax(index * 2, left, mid, st, ed);
	ll rightN = rangeMax(index * 2 + 1, mid + 1, right, st, ed);
	return max(leftN, rightN);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("sample_input.txt","r",stdin);
	int a, b;

	cin >> N >> M;
	init(1, 1, N);
	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		minVal = rangeMin(1, 1, N, a, b);
		maxVal = rangeMax(1, 1, N, a, b);
		cout << minVal << " " << maxVal << "\n";
	}
}

---