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

문제 설명

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

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

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

 

제한 사항

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

 

입출력 예

operations	return
["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

 

문제 풀이

이 문제를 보고 "문자열 파싱" , "자료 구조 선택" 이 먼저 떠올랐다.

1. 문자열 파싱 함수를 만들기

  되도록 한 함수에서는 한가지 기능만 하도록 만들었다. 클린코드!!

  문자열 파싱 함수에서는 파싱만 하기!

2. 자료 구조 선택 : 삽입,삭제가 용이한 자료구조를 사용하기

   문제에서 원하는 행위는 삽입, 최댓값 삭제, 최솟값 삭제, 최댓값 추출, 최솟값 추출 이다.

 

   최댓값, 최솟값은 int 형의 자료구조를 만들어 sort 함수로 정렬시키고

   맨앞과 맨뒤 원소를 가져오면 되겠다고 생각했다.

   --> 여기만 생각하면 vector가 적절하다.

   (vector도 front(), back() 맨앞, 맨뒤 원소 접근 함수가 있다.)

 

   하지만 최댓값 삭제, 최솟값 삭제 기능을 구현하기엔  vector가 적절하지 않다고 판단했다.

    vector는 index가 있어 원소 접근은 빠르지만 중간 원소에 대한 삽입,삭제,수정을 하게 되면 속도가 현저히 떨어진다.

    첫번째 원소(최솟값), 마지막 원소(최댓값)을 삭제하면 erase함수를 사용하게 되는데 이때 재정렬도 해줘야한다.

    (index 관리!!)

   그래서 맨앞과 맨뒤 원소에 대한 삽입, 삭제가 빠른 deque를 선택했다.

 

추가로 deque 변수의 원소에 접근하고자 할때 

비어있는지 검사안하고 바로 접근하게 되면 signal: segmentation fault (core dumped) 오류가 난다.

out of range 때문일것이라 추측된다. 

어떤 자료구조 변수던지 원소에 접근하기 전에 범위 체크하고 접근해야 한다!

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

void OperParse(string str, string& cmd, string& value, const string& delimiter){
    int pos = 0;
    string token("");
    
    while( (pos = str.find(delimiter)) != string::npos ){
        cmd = str.substr(0, pos);
        str.erase(0, pos + delimiter.length());
    }
    value = str;
}

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    deque<int> dq;
    
    string cmd("");
    string value("");
    
    for(string it : operations){
        OperParse(it, cmd, value , " ");
        
        if(cmd == "I"){
            dq.push_back(stoi(value));
        }
        else if(cmd == "D"){
            
            if(dq.empty())  continue;  //dq 가 비었는데 접근할 수 있으니 예외처리 필수!
                                       //dq에 접근 하기전 비어있는지 검사 안하면 
                                       //signal: segmentation fault (core dumped) 오류 난다.
            sort(dq.begin(), dq.end());
            if(value == "1")
                dq.pop_back();
            else
                dq.pop_front();
        }
    }
    
    if(dq.empty())
        return {0,0};

    sort(dq.begin(), dq.end());
    answer.emplace_back(dq.back());
    answer.emplace_back(dq.front());

    return answer;
}