[프로그래머스/알고리즘] 이중우선순위큐

문제 설명

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

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

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

입출력 예

operations ["I 16","D 1"] 

return [0,0]

operation ["I 7","I 5","I -5","D -1"]

return [7,5]

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

해결과정

가장 무식하게 했습니다. I가 있으면 숫자가 들어 오기 때문에 문자를 덱구조에 집어 놓고 정렬하는 방식을 이용했습니다. 또한 D가 있으면 최대값 또는 최솟값이 빠져 나가는데  덱구조의 처음과 끝이 최댓값 최솟값이므로 pop_back또는 pop_front로 쉽게 뺄 수가 있습니다.

그리고 문자를 split함수로 이용해서 뒤에있는 숫자를 뽑아낼 수 있는데 java나 python처럼 편한 함수가 제가 못찾아서 그냥 문자 추출방법인 substr를 이용해서 문자의 3번째부터 끝(string:npos)를 이용해서 숫자를 추출했습니다.

소스코드 

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

vector<int> solution(vector<string> operations) {
 vector<int> answer;
 deque<int> que;
 string temp;
    
 for (int i = 0; i < operations.size(); i++) {
  if (operations[i][0] == 'I') {
   temp = operations[i].substr(2, string::npos);
   int a = stoi(temp);
   que.push_back(a);
  }
  else if (operations[i][0] == 'D') {
   temp = operations[i].substr(2, string::npos);
   int a = stoi(temp);
   if(!que.empty())
    if (a == -1) {
     que.pop_front();
    }
    else if(a == 1) {
     que.pop_back();
    }
  }
 }
  sort(que.begin(), que.end());

 if (que.empty())
  return { 0,0 };
 answer.push_back(que[que.size() - 1]);
 answer.push_back(que[0]);

 return answer;
}