[백준 7662] 이중 우선순위 큐

🔗알고리즘 문제

부족한 반복자의 관한 지식으로 잠시 해맸었 던 문제이다. 이 문제를 통해 내가 미처 몰랐던 부분을 보충하고 넘어갈 수 있었고 새로운 지식을 알게 되어 좋았다.

문제 분석

이 문제를 간단하게 설명한다면 단순히 가장 큰 값과 가장 작은 값에 접근 할 수 있는 priority queue를 만드는 문제이다.

발상 & 알고리즘 설계

문제를 보자마자 priority queue를 활용하여 푸는 문제인가 싶었지만 그러자기엔 맨 앞에 인덱스에 접근하기가 어렵기 때문에 기본적으로 오름차순으로 정렬되는 set 자료구조를 활용하여 문제를 해결하기로 하였다.

코드

#include<iostream>
#include<set>

using namespace std;

struct CustomGreater{
    bool operator()(pair<int,int> a, pair<int,int> b) const {
        return a.second <= b.second;
    }
};

set<pair<int, int>, CustomGreater> doublePriorityQueue;

void CalculateOper(char operation, int operationNum, int index);

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int testCase;
    int operationCount;

    cin >> testCase;

    while(testCase--){
        doublePriorityQueue.clear();

        char operation;
        int operationNum;

        cin >> operationCount;

        for(int i = 0; i < operationCount; i++){
            cin >> operation >> operationNum;
            CalculateOper(operation, operationNum, i);
        }

        if(doublePriorityQueue.empty()){
            cout << "EMPTY" << "\n";
        }
        else{
            cout << (*(--doublePriorityQueue.end())).second << " " << (*doublePriorityQueue.begin()).second << "\n";
        }
    }
}

void CalculateOper(char operation, int operationNum, int index){
    switch(operation){
        case 'I':
            {
                doublePriorityQueue.insert({ index, operationNum });
            }
            break;
        case 'D':
            {
                if(doublePriorityQueue.empty()){
                    return;
                }
                else if(operationNum == 1){
                    doublePriorityQueue.erase(--doublePriorityQueue.end());
                }
                else{
                    doublePriorityQueue.erase(doublePriorityQueue.begin());
                }
            }
            break;
    }
}

추가적인 공부

문제는 set 자료구조를 통해 간단히 해결할 수 있었지만 이 문제를 통해 반복자에 관한 추가내용을 공부할 수 있었다.

[ 5 ], [ 3 ], [ 2 ]

이러한 vector형 배열에서 v.end()를 사용해 반복자를 가져오게 되면 배열에 마지막 값 다음 값을 반환한다는 것은 cpp를 조금만 공부해도 당연히 알고있는 사실이다.

때문에 나는 당연히 v.end() - 1을 하게되면 마지막 값이 반환된다고 생각했지만 이상한 값이 반환되었다.

cout << *(v.end() - 1); // output : ?
cout << *(--v.end()); // output : 2

그 이유를 알기 위해선 연산자의 차이에 대해 다시 한 번 생각해봐야 하는데

int a = 2;

cout << a - 1; // output : 1
cout << a; // output : 2

----------------------

cout << --a; //output : 1
cout << a; //output : 1

이처럼 단지 -1을 해주는 것은 원본 값은 바뀌지 않는 반면 --연산자는 원본 값에 실제로 적용이 되는 연산자이다.

반복자에도 같은 개념이 적용되는데 이로인해 --연산자를 사용하여 실제 한 칸전에 값을 적용해주어야 원하는데로 마지막 값에 접근할 수 있었다.

새로운 지식을 얻어갈 수 있는 문제였다.