이번에 풀어볼 문제는 백준 1927번 최소 힙 문제 입니다.
문제 링크 : https://www.acmicpc.net/problem/1927
원래 문제대로라면 우선순위큐 를 이용하는걸 더 권장 하지만
또다른 힙인 set과 비교해 보려고 이번엔 두가지 풀이를 다 해봤습니다.
우선순위큐 (priority_queue) 풀이
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <stdio.h>
using namespace std;
int main() {
int n;
int temp;
priority_queue<int,vector<int>,greater<int>> pq;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf(" %d", &temp);
if (temp == 0) {
if (!pq.empty()) {
printf("%d\n", pq.top());
pq.pop();
}
else
printf("0\n");
}
else
pq.push(temp);
}
return 0;
}
정말 짧습니다.
참고로 cin 이 아닌 scanf 쓰셔야 시간초과가 안납니다!.
cin 이 매우 편하지만서도, 매우 느린 연산입니다.
그에 반해 scanf 는 조금 불편해도 속도가 매우 빠르지만, 보안상의 문제로
권고 하지는 않는 편인데요, 아직 저희는 그런것 까지 고려하진 않아도 되니
빠른 scanf 를 이용 해 주세요.
우선순위 큐란
힙의 일종입니다.
최소값, 혹은 최대값 만을 찾는데에 특화 되어 있는 트리입니다.
최소값, 최대값 만 맨 위의 루트노드에 올리고, 나머지는 순서는 상관 없지만
아래가 더 크다는 규칙만으로 이루어져 잇습니다.
물론 라이브러리 우선순위 큐는 여기에 더해서
아래 데이터들 정렬에 대한 규칙도 있긴 합니다. ( 쏠림방지)
set 풀이
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <stdio.h>
#include <set>
using namespace std;
int main() {
int n;
int zerocount = 0;
int temp;
multiset<int> ms;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf(" %d", &temp);
if (temp == 0) {
zerocount++;
if (!ms.empty()) {
printf("%d\n", *ms.begin());
ms.erase(ms.begin());
}
else
printf("0\n");
}
else
ms.insert(temp);
}
return 0;
}
위의 우선순위 큐와 상당히 흡사 해 보입니다.
같은 힙(트리)을 사용하기 때문입니다.
주의 하실 점은
그냥 set을 사용하게 되면, 중복 값에 대한 처리가 안되어 정답이 되지 않을겁니다.
그렇다면 백준에 제출 결과는 어떻게 나왔을 까요?
우선순위 큐 : 메모리 : 2380kb 소요시간 : 20ms
set : 메모리 : 4236kb 소요시간 : 46ms
우선 순위 큐가 메모리 면에서나 소요시간 면에서나 훨씬 더 우월 하게 나왔네요!
이렇게 된 이유는
자세히 뜯어 봐야 알겠지만
제가 짐작 하기로는
우선순위큐는 위에서도 말했듯이 제일 최적화된 것만을 찾기 위한 트리이지만
set의 경우에는 맨위가 아닌 아래에서도 찾아 다니는 연산을 해야 합니다.
저희가 아무리 맨 위에값만 쓴다고 해도, 맨 윗 값을 뽑았을 때
아래값이 다 정렬이 되어야 하기 때문에 우선순위 큐가 훨씬 더 빠른 거 같습니다.