[프로그래머스][C++][42628] 이중 우선순위큐

[문제 출처]

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

1. 문제

설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

입출력 예

 

2. 설명

  맨뒤, 맨앞 양쪽에서 숫자를 빼야하므로 deque를 사용해서 구현해보았습니다.

 

 

 먼저 operation에서 명령어와 숫자를 분리하기위해 istringstream을 활용해서 분리해준것을 op에 넣어주었습니다.

 

op[0]=="I" 일경우 큐에 주어진 숫자를 삽입합니다.

 

op[0]=="D"인경우 

- deq가 비었을경우 뺄것이 없으므로 다음으로 넘어갑니다.

- op[1]=="1"인경우 최대값을 삭제하므로 맨뒤값을 삭제합니다.

- op[1]=="-1"인경우 최소값을 삭제하므로 맨앞값을 삭제합니다.

 

정렬을 위해 sort를 실행합니다.

 

모든 연산이 끝났을때 deq이 비어있다면 0,0을 넣어주고 비어있지 않다면 최대값 최소값을 리턴해줍니다.

 

 

3. 코드

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

using namespace std;

vector<string> split(string str){
    istringstream its(str);
    vector<string> a;
    string buffer;
    
    while(getline(its,buffer,' '))
        a.push_back(buffer);
        
    return a;
}

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    vector<string> op;
    deque<int>deq;    
    
    for(int i=0; i<operations.size(); i++){
        op=split(operations[i]);
        if(op[0]=="I"){
            deq.push_back(stoi(op[1]));
        }
        else if(op[0]=="D"){
            if(deq.empty()==1)
                continue;
            
            if(op[1]=="1")
                deq.pop_back();
            else if(op[1]=="-1")
                deq.pop_front();
        }
        sort(deq.begin(), deq.end());
    }
    
    if(deq.empty()==1){
        answer.push_back(0);
        answer.push_back(0);
    }
    else{
        answer.push_back(deq.back());
        answer.push_back(deq.front());
    }
   
    
    return answer;
}