[백준] #7662. 이중 우선순위 큐

문제는 여기서 확인할 수 있다. BaekJoon #7662. 이중 우선순위 큐

---

💀 시행착오

👇 풀이를 보러 온거라면 아래에 POINT로 바로 내려가면 된다. 👇

문제를 마주하면 항상 어떻게 최대한 빠르고 간편하게 풀지 머리를 굴리게된다.
보자마자 priority queue를 써야겠다는 생각이 들었지만 시간 제한이 6초나 되는데 벡터로는 어떻게 안될까 머리를 굴려봤다.

• 입력은 그냥 push_back()해서 넣어버리고
• 출력 요청이 들어오면 sort()하고 맨 앞, 또는 맨 뒤 숫자를 erase()

하지만 역시나 시간 초과~~~
sort 함수는 quick sort 알고리즘으로 만들어졌기 때문에 시간 복잡도는 O(NlogN)이다. 해당 문제에서 연산은 최대 1,000,000번 수행될 수 있다. 게다가 백터의 가장 첫 번째 수를 지우는vector::erase(vector.begin()) 연산은 벡터의 사이즈만큼의 시간이 필요하다.

결론 : 아무리 6초여도 벡터는 에바 비효율적이다.

---

🤔 POINT

최댓값 최솟값만 쏙쏙 뽑아낼 수 있는 자료구조가 보이면 Heap 자료구조가 가장 먼저 떠올릴 수 있다. 트리 형태의 자료구조로 Max Heap은 부모가 자식보다 크거나 같은 값을 갖는 조건을 만족하고 Min Heap은 부모가 자식보다 작거나 같은 값을 갖는다.

1. Heap

Max Heap은 부모가 자식보다 크거나 같은 값을 갖는다.

• push가 되면 가장 끝 노드에 추가가 되고 조건을 만족하도록 정렬이 이루어진다. 새로운 노드를 부모 노드와 비교하면서 부모 노드보다 값이 크면 swap해서 올라간다. 트리 구조이기 때문에 시간 복잡도는 O(logN)이다.
  

• pop은 Max Heap의 가장 큰 값을 꺼낸다. Root와 가장 마지막 노드를 swap한다. push할 때와는 반대로 Root노드와 자식 노드들의 값을 비교해서 가장 큰 값이 부모 노드로 올라오도록 swap한다. 마지막 노드로 옮겨둔 Max 값을 리턴하고 길이를 하나 줄여서 노드를 없앤다.
  

2. priority queue

트리를 직접 구현하는 것도 좋은 방법이지만 Heap을 사용하는 문제에서는 priority queue를 사용할 수 있다.
priority queue 구현 관련해서는 나중에 글을 하나 더 써서 링크를 연결해둘 것 같다.(까먹고 못할지도...)
간단한 소개만 하자면

• priority_queue<type, Container Type, Compare> 로 정의
• 기본적으로 Min Heap이며 Max Heap은 Compare 함수에 greater<Type>을 사용하면 된다.
• Type이 pair인 경우 첫번째 값을 비교해 정렬한다.
• 관련함수는 queue와 유사하다.

---

3. 풀이 과정

같은 값을 저장하는 Min Heap과 Max Heap을 각각 만들었다.

priority_queue<pair<int, int>> max_heap;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> min_heap;

Insert는 두 Heap 모두에 push 해준다. 한 Heap에서 지워지면 다른 Heap에서도 지워져야하지만 바로 지울 수는 없으니 bool 타입의 valid 배열에 체크를 해준다.

case 'I':
	min_heap.push(make_pair(num, q));
	max_heap.push(make_pair(num, q));
	valid[q] = true;
   	break;

Delete는 0이 들어오면 Max Heap에서 pop하고 valid를 false로 바꾼다. -1이 들어오면 Min Heap에서 pop하고 똑같이 valid를 false로 바꿔 체크한다.
Heap에서 pop하기 전에 이미 그 값이 valid에서 false 되었을지도 모르니 싱크를 맞춰준다.

case 'D':
	if(num > 0){
		sync_max_heap(valid, max_heap);
		if(!max_heap.empty()){
			valid[max_heap.top().second] = false;
			max_heap.pop();
            }
		}
	else{
    	sync_min_heap(valid, min_heap);
		if(!min_heap.empty()){
			valid[min_heap.top().second] = false;
            min_heap.pop();
		}
	}
    	break;

싱크를 맞추는 거는 그냥 top에 있는 값이 valid하지 않으면 pop해서 버리는 방식이다. 간단😉

void sync_max_heap(bool valid[], priority_queue<pair<int, int>> &max_heap){
    while(!max_heap.empty() && !valid[max_heap.top().second]){
        max_heap.pop();
    }
    return;
}

전체 코드는 아래와 같다.

//BaekJoon_7662
//이중 우선순위 큐
/*
* 제한 시간 : 6s
* 정답 비율 : 24.621%
*/

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// 두 힙의 싱크를 맞추는 함수
void sync_max_heap(bool valid[], priority_queue<pair<int, int>> &max_heap){
    while(!max_heap.empty() && !valid[max_heap.top().second]){
        max_heap.pop();
    }
    return;
}

void sync_min_heap(bool valid[],  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> &min_heap){
    while(!min_heap.empty() && !valid[min_heap.top().second]){
        min_heap.pop();
    }
    return;
}

// 입력되는 명령을 처리
void make_pq(int quest, priority_queue<pair<int, int>> &max_heap,  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> &min_heap){
    bool valid[1000001];
    char order; int num = 0;

    for(int q=0; q<quest; q++){
        scanf("%c %d", &order, &num);
        switch(order){
        case 'I':
            min_heap.push(make_pair(num, q));
            max_heap.push(make_pair(num, q));
            valid[q] = true;
            break;
        case 'D':
            if(num > 0){
                sync_max_heap(valid, max_heap);
                if(!max_heap.empty()){
                    valid[max_heap.top().second] = false;
                    max_heap.pop();
                }
            }
            else{
                sync_min_heap(valid, min_heap);
                if(!min_heap.empty()){
                    valid[min_heap.top().second] = false;
                    min_heap.pop();
                }
            }
            break;
        default :
            q--;
            break;
        }
    }

    sync_min_heap(valid, min_heap);
    sync_max_heap(valid, max_heap);

    return;
}

void print_result(priority_queue<pair<int, int>> &max_heap,  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> &min_heap){
    if(max_heap.empty()){
        printf("EMPTY\n");
    }
    else{
        printf("%d %d\n", max_heap.top().first, min_heap.top().first);
    }
    return;
}

int main(){
    int testcase = 0;
    scanf("%d", &testcase);
    
    while(testcase--){
        int quest = 0;
        priority_queue<pair<int, int>> max_heap;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> min_heap;
        scanf("%d", &quest);

        make_pq(quest, max_heap, min_heap);
        print_result(max_heap, min_heap);
    }

    return 0;
}

---

주저리

나홀로 solved.ac 챌린지하면서 문제를 푸는데 중간중간 삽질한 문제, 잘못 생각해서 시간을 잡아먹은 문제, 어려워서 새로 배운게 있는 문제들은 개별 글로 올려보기로 했다! 쉬운건 글로 쓰기에는 너무 사소해서 중간중간 몇문제씩 묶어서 리뷰해야지ㅎ

끝 ✌