본문 바로가기

Archived(CSE Programming)/알고리즘(C++)

프로그래머스_이중우선순위큐

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

 

코딩테스트 연습 - 이중우선순위큐 | 프로그래머스

 

programmers.co.kr

해당 문제는 이중우선순위큐이다.

C++에 물론 priority_queue를 제공하긴 하지만 

이중우선순위큐를 구현하려면 deque을 통해 정렬을 하면서 접근하는 방식이 보다 쉬울 듯하여 구현하였다.

삽입은 삽입 후에 꼭 정렬을 해줘서 우선순위를 지켜야 한다.

그리고 삭제는 최소값인지 최대값인지에 따라 pop_front, pop_back을 수행한다.

#include <string>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

vector<int> solution(vector<string> opers) {
    vector<int> answer;
    deque<int> d;
    
    // 명령어 처리
    for(int i=0;i<opers.size();i++){
        // CASE 1 삽입
        if(opers[i][0] == 'I'){
            string val_s = opers[i].substr(2, opers[i].size()-2);
            int val = stoi(val_s);
            d.push_back(val); // 삽입
            sort(d.begin(), d.end()); // 오름차순 정렬
        }
        
        // CASE 2 최소값 삭제
        else if(opers[i][2] == '-'){
            // 비어있을 경우
            if(d.empty())
                continue;
            
            d.pop_front(); // 최소값 삭제
        }
        // CASE 3 최대값 삭제
        else{
            // 비어있을 경우
            if(d.empty())
                continue;
            
            d.pop_back(); // 최대값 삭제
        }
    }
    
    // 원소 0개
    if(d.empty()){
        answer.push_back(0);
        answer.push_back(0);
    }
    
    // 원소 1개
    else if(d.size()==1){
        answer.push_back(d.front());
        answer.push_back(d.front());
    }
    
    // 원소 2개 이상
    else{
        answer.push_back(d.back());
        answer.push_back(d.front());
    }
    
    return answer;
}