백준 14427: 수열과 쿼리 15

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

 

백준 내에서 "수열과 쿼리 시리즈"는 보통 세그먼트 트리로 해결할 수 있는 문제들이 즐비된 시리즈이다.

대표적으로 세그먼트를 활용한 머지 소트 트리란 자료구조를 처음으로 알게 해준 13537: 수열과 쿼리 1,

합 세그먼트 트리를 활용한 16978: 수열과 쿼리 22 등등이 있다.

 

이 문제 또한 세그먼트 트리로 해결할 수 있다. 처음 봤을 때부터 떠오른 생각은 그것이였다.

문득 이 문제는 세그먼트 트리를 사용하지 않아도 풀 수 있을 지 않을까? 생각이 들기 시작했다.

이 문제에서 주어진 명령어 2는 다른 문제들과 다르게 수열 범위를 지정하지 않고, 단순히 전체 범위만을 나타낸다 그렇다면, 다른 해결 방법이 있을 것이다.

 

수열 내에서 가장 작은 값을 찾는 방법은 몇가지가 있다.

첫 째는 방금 언급한 세그먼트 트리다.

둘 째는 쿼리 때마다 수열을 탐색하는 방법이지만, 최악의 경우 O(N^2)의 시간 복잡도를 지니므로 이 방법은 아니다.

셋 째는 sort하는 법이지만, 이것은 O(N ^ 2 * log N)로 더욱 최악이다.

마지막은 우선순위 큐를 활용하는 법이다. 최소 우선 순위 큐에 (배열 값, 인덱스)를 저장한 뒤 가장 작은 값을 가져오는 방식이다.

 

이 방법에서 고민해야할 것은 쿼리를 어떻게 처리할 것인가?다.

일단 우선 순위 큐에 넣어볼까? 그렇다면 기존에 우선 순위 큐에 남아있는 원소는 어떻게 해야할까?

우선 순위 큐의 값과 현재 배열의 값을 비교해서 다르면 pop하면 될것이다.

 

#include <iostream>
#include <queue>

using namespace std;

int N, A[100001], M, C, I, V;
priority_queue<pair<int, int>> pq;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> A[i];
		pq.push({ -A[i], -i });
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> C;
		if (C == 1)
		{
			cin >> I >> V;
			A[I] = V;
			pq.push({ -V, -I });
		}
		else
		{
			while (!pq.empty() && A[-pq.top().second] != -pq.top().first)
				pq.pop();
			cout << -pq.top().second << '\n';
		}
	}
}

세그먼트 트리보다 훨씬 간단하게 코드를 구성할 수 있게 되었다.