[프로그래머스] 이중우선순위큐(Lv3/C++)

 

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

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

코드 설명

기존에는 문제처럼 priority_queue 두개를 할당해서 구현하다가 문제를 깨달았다. 큐를 두개 할당하고 문제를 풀때 최댓값을 지우고 최솟값을 지우는 과정에서 없어져야 할 숫자가 계속 남는 문제가 생긴다

(이를 해결하려면 cnt변수를 할당해서 넣고 빼는 횟수가 같다면 큐를 전부 비워주어야한다)

 

그래서 저는 아예 vector 하나에 할당하여 매번 sort시켜주고 앞,뒤에서 각각 빼주는 방식을 생각하였습니다. (시간복잡도는 더 늘어날듯..)

 

코드

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
  vector<int> result;
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    for(int i=0;i<operations.size();i++){
        bool I_flag=false;
        bool D_flag=false;
        string abc="";
        for(int j=0;j<operations[i].size();j++){
            
            if(operations[i][j]=='I'){
                I_flag=true;
                
            }
            else if(operations[i][j] == 'D'){
                D_flag=true;
                
            }
            else if(I_flag==true && operations[i][j]!=' '){
                abc+=operations[i][j];
            }
             else if(D_flag==true && operations[i][j]=='-'){ //최솟값삭제
                if(answer.size()>0)
                answer.erase(answer.begin());
                 break;
            }
            
            else if(D_flag==true && operations[i][j]=='1'){ //최댓값삭제
                if(answer.size()>0){
                    answer.erase(answer.begin()+answer.size()-1);
                }
            }
           
        }
        if(abc!=""){
            answer.push_back(stoi(abc));
 
        }
        sort(answer.begin(),answer.end());
    }
    
    if(answer.size()==0){
        result.push_back(0);
        result.push_back(0);
    }
    else{
    int N=answer.size();
  
    result.push_back(answer[N-1]);
    result.push_back(answer[0]);
    }
    return result;
}