[프로그래머스:고득점kit] 이중우선순위큐

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

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

레벨: 3

 

문제 요약:

스트링을 입력받아서

- I 숫자: 삽입

- D -1 : 최솟값 삭제

- D 1 : 최댓값 삭제

를 진행한 후 [최댓값, 최솟값] 배열을 리턴한다. 없는 경우 [0,0]을 리턴한다.

 

문제 풀이:

제목이 우선순위큐인만큼 우선순위큐를 사용한다. 최대힙과 최소힙을 선언한 후 I가 들어온다면 힙 모두에 삽입을 한 후 숫자를 카운트한다.

cnt를 사용해서 동기화를 진행한다.

 

#include <bits/stdc++.h>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    priority_queue<int> maxh;
    priority_queue<int, vector<int>, greater<int>> minh;
    int cnt = 0;
    for(string s: operations){
        
        if(cnt == 0){
            while(!minh.empty()) minh.pop();
            while(!maxh.empty()) maxh.pop();
        }
        
        string op = s.substr(0,1);
        int num = stoi(s.substr(2,s.length()-2));
        if(op == "I"){
            minh.push(num);
            maxh.push(num);
            cnt++;
        }else {
            
            if(cnt == 0){
                continue;
            }
            
            if(num == 1){
               maxh.pop();
            }else{
                minh.pop();
            }
            cnt--;
        }
    }
    
    if(cnt == 0){
        answer.push_back(0);
        answer.push_back(0);
    }else {
        answer.push_back(maxh.top());
        answer.push_back(minh.top());
    }
    return answer;
}