[프로그래머스] 힙(Heap) > 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

[해결방법]

1. 문자열을 쪼갠다.

2. asc 로 정렬되는 queue 하나와 desc로 정렬되는 queue 하나를 사용한다.

3. push가 들어오면 인자의 갯수를 카운트하는 cnt를 하나 올린다.

4. pop_max 가 들어오면 max 의 값을 pop해주고 cnt--해준다.

- cnt == 0 가 되면 큐에 인자들이 더이상 없는 것이므로 큐 두개를 다 clear 해준다.

5. pop_min 가 들어오면 min 의 값을 pop해주고 cnt--해준다.

- cnt == 0 가 되면 큐에 인자들이 더이상 없는 것이므로 큐 두개를 다 clear 해준다.

6. 모든 명령어를 처리하고나면 최댓값, 최솟값을 벡터에 담아 리턴해준다.

 

cnt == 0 일때 정리해주지 않으면 1번 케이스를 틀린다.

자동으로 정렬이 되는 자료구조를 원한다면 set 이나 priorirty_queue 를 사용하여 구현할 수 있다.

 

[전체코드]

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

priority_queue <int, vector<int>, greater<int>> small;
priority_queue <int, vector<int>> big;
int cnt = 0;
// 양수, 음수

void clear_pq() {
    while(!small.empty()) {
        small.pop();
    }
    while(!big.empty()) {
        big.pop();
    }
}

void push(int no) {
    cnt++;
    big.push(no);
    small.push(no);
}
   
void pop_max() {
    if(cnt==0) return;
    big.pop();
    if(--cnt == 0) {
        clear_pq();
    }
}

void pop_min() {
    if(cnt==0) return;
    small.pop();
    if(--cnt == 0) {
        clear_pq();
    }
}


vector <int> finish() {
    vector <int> v(2, 0);
    if(cnt <= 0)
        return v;
    
    v[0] = big.top();
    v[1] = small.top();
    
    return v;
}


vector<int> solution(vector<string> operations) {
    vector<int> answer;

    for(auto operation : operations) {
        
        char op; int value;
        sscanf(operation.c_str(), "%c %d", &op, &value);
        if(op == 'I') {
            push(value);
        }
        else if(op == 'D') {
            if(value == 1)
                pop_max();
            else 
                pop_min();
        }
    }
    return finish();
}