https://www.acmicpc.net/problem/7662
이름 처럼 우선순위큐를 반드시 두개 사용해야 풀 수 있다.
1 2 3 4 가 값으로 들어온다면,
하나의 큐는 1 2 3 4 순으로
다른 하나의 큐는 4 3 2 1 순으로 우선순위가 구성되어야 한다. 즉, 최대힙과 최소힙이 필요하다.
아이디어 1.
언제나 최대힙의 top > 최소힙의 top 이면 되지 않을까
즉, 만약 최대힙에서 pop을 3번, 최소힙에서 pop을 1번 하게 되면 최대힙의 top은 1이고 최소, 힙의 top은 2이다.
위의 원칙을 어겼다. 이 뜻은 이미 최소힙의 top은 최대힙에서 pop되었다는 의미이기 때문이다. 하지만 이 방법은 20퍼센트에서 틀렸습니다를 받았다.
만약 모든 수가 다르다는 조건이 있었다면 맞았을 지 모르겠으나 만약
1 1 1 1 이 들어오고 2번의 최소힙 최대힙 pop이 들어오면 원래는 EMPTY가 출력되어야하지만 위의 논리대로면 이 조건을 해결할 수 없다. 한번만 pop이 되어도 최대힙의 top이 더 크지 않다고 하여 초기화되어 버릴 것이다.
정해: 갯수를 저장해두자.
갯수를 저장해두는 맵을 떠올리는 것이 핵심인 문제였다. 만약 1 1 1 1 이 들어왔다면 map[4] = 4 이고 큐에서 1이 pop될때마다 1의 갯수를 줄여준다.
그리고 pop한 후 두 개의 큐를 검사하여 만약 top이 허수라면 지워준다.
이 문제의 연산 개수는 1,000,000 이다. 그리고 우선순위큐의 시간복잡도는 삽입삭제 모두 log(N)을 갖는다.
백만 * log 백만 * (top이 카운트인지 세는 연산까지) 하면... 대체 시간복잡도가 말이 되는 건가?
라고 생각했는데 1.5초에 통과됐다;
이렇게 중간에 반복이 돌게되는 문제의 시간복잡도 계산은 너무 어려운 것 같다..
그리고 다른 C++ 코드들은 int로 돌아가던데 난 long 으로 돌려야 통과가 되었다. STL의 우선순위큐에 무언가 오버플로가 걸리는 것 같다.
*
원인을 알았다..!!
short | -32,768 ~ 32,767 |
ushort | 0 ~ 65,535 |
int | -2,147,483,648 ~ 2,147,483,647 |
uint | 0 ~ 4,294,967,295 |
정수형의 범위를 보면 MIN_INT 의 절댓값이 MAX_INT 보다 1 크다. 그러므로 내 방법대로 하면 -value 했을 때 정수형의 범위를 넘어버리는 것이었다!!
지금까지 모든 우선순위큐 문제를 이렇게 풀었는데.... 모두 값의 범위가 이렇게 크지 않았던 문제들이어서 그랬던 것이다.
오늘 하나 배웠다.
*
#include <iostream>
#include <queue>
#include <map>
#define ll long long
using namespace std;
map<ll, int> cnt;
priority_queue<ll> pq;
priority_queue<ll> rev_pq;
void MaxdeleteQueue(){
if(!pq.empty()){
cnt[pq.top()]--;
pq.pop();
}
while(!pq.empty() && cnt[pq.top()] == 0){
pq.pop();
}
while(!rev_pq.empty() && cnt[-rev_pq.top()] == 0){
rev_pq.pop();
}
}
void MindeleteQueue(){
if(!rev_pq.empty()){
cnt[-rev_pq.top()]--;
rev_pq.pop();
}
while(!pq.empty() && cnt[pq.top()] == 0){
pq.pop();
}
while(!rev_pq.empty() && cnt[-rev_pq.top()] == 0){
rev_pq.pop();
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T; cin >> T;
for(int t = 0; t < T; t++){
int N; cin >> N;
while(!pq.empty()) pq.pop();
while(!rev_pq.empty()) rev_pq.pop();
cnt.clear();
for(int i = 0; i < N; i++){
char op;
ll value;
cin >> op >> value;
if(op == 'I'){
pq.push(value);
rev_pq.push(-value);
cnt[value]++;
}else if(op == 'D'){
if(value == 1){
MaxdeleteQueue();
}else{
MindeleteQueue();
}
}
}
while(!pq.empty() && cnt[pq.top()] == 0){
pq.pop();
}
while(!rev_pq.empty() && cnt[-rev_pq.top()] == 0){
rev_pq.pop();
}
if(pq.empty() || rev_pq.empty()){
cout << "EMPTY" << '\n';
continue;
}
cout << pq.top() << ' ' << -rev_pq.top() << '\n';
}
}
'백준 문제 풀이' 카테고리의 다른 글
백준 1644번 - 소수의 연속합 (C++, 에라토스테네스의 체, 누적합, 투포인터) (0) | 2024.08.13 |
---|---|
백준 16472번 - 고냥이(C++) (0) | 2024.08.06 |
백준 1474번 - 밑 줄(java, 그리디, 구현) (0) | 2024.06.27 |
백준 1477번 - 휴게소 세우기 (Java) (0) | 2024.06.27 |
백준 1516번 - 게임 개발 (C++, 위상정렬, 다이나믹 프로그래밍) (0) | 2024.06.22 |