프로그래머스 LV.3 이중우선순위

GitHub :

https://github.com/kwon1232/CodingTest/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/3/42628.%E2%80%85%EC%9D%B4%EC%A4%91%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%ED%81%90

CodingTest/프로그래머스/3/42628. 이중우선순위큐 at main · kwon1232/CodingTest

 

 

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int> maxHip;
    priority_queue<int, vector<int>, greater<int> > minHip;

    for (int i = 0; i < operations.size(); i++)
    {
        string num = "";
        if (operations[i][0] == 'I')
        {
            num += operations[i].substr(2, operations[i].length());
            maxHip.push(stoi(num));
            minHip.push(stoi(num));
        }
        else
        {
            // 최솟값 삭제
            if (operations[i][2] == '-')
            {
                if (!minHip.empty())
                {
                    minHip.pop();
                }
                if (!maxHip.empty())
                {
                    int gap = maxHip.size() - minHip.size();
                    priority_queue<int> swapMaxHip;
                    for (int j = 0; j < maxHip.size() - gap; j++)
                    {
                        swapMaxHip.push(maxHip.top());
                        maxHip.pop();
                    }

                    maxHip.swap(swapMaxHip);

                }
            }
            // 최대 힙 삭제
            else
            {
                if (!maxHip.empty())
                {
                    maxHip.pop();
                }
                if (!minHip.empty())
                {
                    int gap = minHip.size() - maxHip.size();
                    priority_queue<int, vector<int>, greater<int> > swapMinHip;
                    for (int j = 0; j < minHip.size() - gap; j++)
                    {
                        swapMinHip.push(minHip.top());
                        minHip.pop();
                    }
                    minHip.swap(swapMinHip);
                }
            }
        }
    }

    if (!maxHip.empty())
    {
        answer.emplace_back(maxHip.top());
    }
    else
    {
        answer.emplace_back(0);
    }
    if (!minHip.empty())
    {
        answer.emplace_back(minHip.top());
    }
    else
    {
        answer.emplace_back(0);
    }

    return answer;
}

 

 

우선 순위 큐 2개 쓰기
오름차순 내림차순 정렬로 된 것

일단 내림차순 top 먼저 출력하고, 그 뒤에 오름차순 top 출력한다.

1. 최대 힙 삭제의 경우
최소 힙이 삭제되지 않았다면,
최대 힙size에서 최소 힙 size갭 이전 까지의 값들을 pop해준다
그 값들을 임시로 저장해준다.
최대 힙을 비워준다.
임시 배열 혹은 동일 조건 우선순위큐에 저장해준다.

3 2 -15 -16
-16 -15 2 3

2 -15 -16
-16 -15 2 3

temp = -16 -15 2
최소힙 비우기
최소힙 = temp



2. 최소 힙 삭제의 경우

3 2 -15 -16
-16 -15 2 3

3 2 -15 -16
-15 2 3

최대 힙 size에서에서 최소 힙과의 size 차이만큼 빼준 값까지 

pop을 해준다.
그 값을 저장해준다

temp = -15 2 3
최소 힙을 비워준다
최소 힙 = temp

 

3. 값을 넣어주는 경우

 

최소힙 최대힙 둘 다에 값을 넣어준다.

 

4. 둘 다 비어있다면 0,0 출력

 

5. 그렇지 않다면

먼저, 최대힙 top 을 answer에 0번 인덱스에 대입하고

그 뒤에 최소힙 top을 answer에 1번 인덱스에 대입해준다.