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

문제 링크

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

 

 

 

풀이

우선순위 큐를 이중으로 하라는 문제같은데 front와 back 모두 pop과 push를 할 수 있는 deque 컨테이너를 사용해서 풀었다.

(물론 vector의 erase로 front()를 지울 수 있지만, 하나 지우면 복사해서 다시 당겨오기 때문에 비효율적이다)

 

// init

answer[0] = 0, answer[1] = 0

덱(deque) 선언

 

// process

삽입과 삭제로 나눈 후, 삭제는 최댓값 삭제와 최솟값 삭제로 나눈다.

반복문(연산 목록)

{

    삽입

    {

        deque 뒤에 push

        정렬(오름차순)

    }

    삭제

    {

        최대값 삭제: 뒤의 원소 pop

        최소값 삭제: 앞의 원소 pop

    }

}

 

만약, dq가 비어있지 않을 경우

{

    answer에 최대값 삽입: deque의 뒤의 원소 push

    answer에 최소값 삽입: deque의 앞의 원소 push

}

 

리턴!

 

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

using namespace std;

// | 숫자 : 큐에 삽입
// D 1 : 최댓값 삭제
// D -1 : 최솟값 삭제

// 연산 목록 operations

vector<int> solution(vector<string> operations) {
    // init
    vector<int> answer(2, 0);
    deque<int> dq;
    
    // process
    for(string s: operations){
        if(s[0]=='I'){      // 삽입
            int num = stoi(s.substr(2));
            dq.push_back(num);
            sort(dq.begin(), dq.end());        // 오름차순 정렬
        }
        else{     // 삭제
            if(dq.empty()) continue;      // 비어있을 경우 연산 무시
            if(s[2]=='-'){      // 최솟값 삭제
                dq.pop_front();
            }
            else{           // 최댓값 삭제
                dq.pop_back();
            }
        }
    }
    if(!dq.empty()){        // 비어있지 않으면
        answer[0] = dq.back();      // 최대값
        answer[1] = dq.front();     // 최소값
    }
    
    return answer;      // 큐가 비어 있으면 [0, 0] or 비어 있지 않으면 [최댓값, 최솟값] 리턴
}