[프로그래머스]이중우선순위큐 - 힙

문제

[링크] 프로그래머스 이중우선순위큐

아이디어

• 처음에는 priority_queue로 풀려고 했는데 생각해보니 priority_queue는 index를 직접 접근을 못하는걸로 알고 있다

• 그래서 앞뒤로 삽입,삭제 가능한 deque를 사용하기로함

• string 이 값이므로 일단 D인지 I인지를 구문해야함

• 구분한후 뒤에 숫자는 문자이기에 string 헤더를 넣어서 stoi(문자열을 숫자로 바꿔주는 함수) 사용

풀이 순서

1. 일단 I가 나오는 경우는 삽입 후 소팅 바로 함 (오름차순)
2. D인경우 중 문제에서 보면 비어있는데 삭제 하려는 경우는 무시하라고 함 -> 여기에서 비어있지 않은 경우 연산을 하도록 조건 걸어줌
   1. 1이면 가장 큰 값 삭제
   2. -1 이면 가장 작은 값 삭제
3. 큐가 비어있는경우 0,0 강제로 넣음
4. 큐에 값이 있는 경우 가장 큰 수, 가장 작은 수 순으로 넣음

코드

#include <string>
#include <vector>
#include<queue>
#include<string>
#include<iostream>
#include<cstdio>
#include<functional>
#include<deque>
#include<algorithm>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    deque<int> dq;
    for(int i=0;i<operations.size();i++){
        string s=operations.at(i);
        int num = stoi(s.substr(2, s.length()-2));

        if(s[0]=='I'){
            dq.push_back(num);
            sort(dq.begin(),dq.end());
        } else if(!dq.empty()) {
              if (num==1){
                dq.pop_back();
                } else if (num == -1){
                dq.pop_front();
            }
        }
    }
    if(dq.empty()){
        answer.push_back(0);
        answer.push_back(0);
    } else {
        answer.push_back(dq.back());
        answer.push_back(dq.front());
    }
    return answer;
}

정답확인

깃 링크

[링크] 이중우선순위큐-프로그래머스