우선순위 큐와 벡터 정렬 시간복잡도 차이

가끔 알고리즘 문제를 풀다보면 정렬하는 과정이 필요한 문제가 있습니다.

우선순위 큐

문제를 푸는 과정 중에서 원소의 삽입과 삭제를 할 때마다 정렬이 필요한 경우에는

Priority Queue 자료구조를 이용하여 쉽게 구현할 수 있습니다.

벡터

정렬된 결과가 필요할 때 array나 vector을 sort함수를 이용해 쉽게 정렬해줄 수 있습니다.

우선순위 큐 VS 벡터 Sort

그런데 특정 결과를 얻기 위해서 모든 원소를 한번 정렬해준 결과가 필요할 때

과연 우선순위 큐를 이용해서 pop해주면서 순서대로 사용하는 것과

벡터를 이용해서 한번 nlogn 으로 sort 해주는 것 중

어떤게 더 시간복잡도 상에서 빠른지 궁금해졌습니다.

https://stackoverflow.com/questions/3759112/whats-faster-inserting-into-a-priority-queue-or-sorting-retrospectively

결론

내용을 간단히 정리하면

자료 형태나 문제에 따라 다르겠지만

우선순위 큐에 n개의 항목을 삽입 하는 것은

점근적 복잡도 O(nlogn)를 가지므로 복잡도 측면 에서 결국 한 번 사용하는 것보다 효율적이지 않습니다.

즉 정렬이 최종적으로 한번 만 필요한 경우에는

vector 나 array를 한 번 sort 해주는 게 효율적입니다.

반대로 원소의 삽입과 pop이 빈번한 경우는 우선순위큐를 이용해

효율적으로 알고리즘을 구성할 수 있습니다.

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

1.문제설명

#include <bits/stdc++.h>
using namespace std;

int n;
bool ch[1001];
struct Hw {
	int day, point;
	bool operator<(const Hw& b) const {
		return point > b.point;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	vector<Hw> v;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}

	sort(v.begin(), v.end());

	int ans = 0;
	for (int i = 0; i <v.size(); i++) {
		int day = v[i].day;
		int point = v[i].point;

		while (ch[day] && day>=1) {
			day--;
		}
		if (day == 0) continue;
		ch[day] = 1;
		ans += point;
	}
	
	cout << ans << '\n';
	return 0;
}

2. 우선순위 큐 활용

#include <bits/stdc++.h>
using namespace std;

int n;
bool ch[1001];
struct Hw {
	int day, point;
	bool operator<(const Hw& b) const {
		return point < b.point;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	priority_queue<Hw> Q;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		Q.push({ a,b });
	}

	int ans = 0;
	while (!Q.empty()) {
		int day = Q.top().day;
		int point = Q.top().point;
		Q.pop();

		while (ch[day] && day>=1) {
			day--;
		}

		if (day == 0) continue;
		ch[day] = 1;
		ans += point;


	}

	cout << ans << '\n';

	return 0;
}

우선순위큐를 이용해서 삽입할 때마다 바로 정렬을 해주거나

벡터를 이용해서 최종적으로 정렬을 해주거나

문제를 푸는데는 큰 차이가 없어보입니다.