문제 : https://programmers.co.kr/learn/courses/30/lessons/42628

서론

제목에 나와있듯 우선순위 큐를 이용한 문제.

이중우선순위 큐를 이용하려면 최대힙, 최소힙 두개의 우선순위 큐를 만들면 될듯하지만 STL의 우선순위 큐는 인덱스를 이용한 접근이 안된다. 벡터의 위엄이다.

어쨌든 그래서 생각한 방법은

1. 우선순위 큐를 배열로 구현한다.

2. 우선순위 큐를 이용하지 않는다.

3. 다른분의 풀이를 참고한다.

2번을 선택했는데,

우선순위 큐를 만들지 않고 단순히 벡터를 만들고 삽입할떄마다 정렬해주고 최대값 삭제하려면 가장 뒤의 값을, 최소값 삭제하려면 가장 앞의 값을 지우는 형태로 풀었더니 효율성체크가 없어서 통과했다.

그래도 개운치 않아서 우선순위 큐를 이용해서 다시 풀었다.

인덱스를 이용한 엑세스 부분의 해결책은 다른분의 풀이를 참고했다.

풀이

# 우선순위 큐를 이용한 풀이

최대힙과 최소힙을 만드는데, 인덱스가 들어갈 수 있도록 pair로 만들어준다.

operation의 명령어가 삽입이면 최대힙과 최소힙에 주어진 숫자와 고유 번호인 인덱스값을 넣어준다.

for (auto i : operations) {
	if (i[0] == 'I') {
		maxHeap.push({ 주어진 숫자, num });
		minHeap.push({ 주어진 숫자, num });
		num++;
	}

	...

}

op의 명령어가 최대값 삭제라면 최대힙의 인덱스를 배열에 기억하고 pop한다.

인덱스는 최소힙에서도 삭제해주기 위함이다.

최소값 삭제도 마찬가지 방법이다.

for (auto i : operations) {
	...

	else if (i[2] == '1') {
		if (!maxHeap.empty()) {
			del[maxHeap.top().second] = 1;
			maxHeap.pop();
		}
	}

	...
}

op의 명령이 하나 끝나면 최대힙과 최소힙에서 최대/최소값 삭제에서 기억했던 인덱스에 해당하는 힙들을 버려야한다.

현재 최대/최소힙의 top이 버려져야할 인덱스라면 버리고 아니라면 그대로 둔다. (만약 명령이 최대힙 삭제였다면 위에서 최대힙 삭제는 이미 했기 때문에 최소힙에서만 동작한다.) top이 버려져야할 인덱스가 아니라서 내부에 버려져야할 힙이 그대로 있더라도 놔둔다. 나중에 버려질 수도 있고 끝까지 안버려지는것은 모든 명령이 끝났을때 최대/최소값이 아니므로 버려지지 않아도 상관없다.

for (auto i : operations) {

	...

	while (!minHeap.empty() && del[minHeap.top().second] == 1) {
		minHeap.pop();
	}
	while (!maxHeap.empty() && del[maxHeap.top().second] == 1) {
		maxHeap.pop();
	}
}

구현

# 우선순위 큐를 이용한 풀이

// c++

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

using namespace std;
int del[1000000];

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    priority_queue<pair<int, int>>maxHeap;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>minHeap;
    int num = 0;
    for(auto i : operations){
        if(i[0] == 'I') {
            i.erase(0, 2);
            maxHeap.push({atoi(i.c_str()), num});
            minHeap.push({atoi(i.c_str()), num});
            num++;
        }
        else if(i[2] == '1') {
            if(!maxHeap.empty()){
                del[maxHeap.top().second] = 1;
                maxHeap.pop();
            }
        }
        else if(i[2] == '-'){
            if(!minHeap.empty()){
                del[minHeap.top().second] = 1;
                minHeap.pop();
            }
        }
        
        while(!minHeap.empty() && del[minHeap.top().second] == 1){
            minHeap.pop();
        }
        while(!maxHeap.empty() && del[maxHeap.top().second] == 1){
            maxHeap.pop();
        }
    }
    
    if(maxHeap.empty()) answer.push_back(0);
    else answer.push_back(maxHeap.top().first);
    if(minHeap.empty()) answer.push_back(0);
    else answer.push_back(minHeap.top().first);
    
    return answer;
}

# 정렬을 이용한 풀이

// c++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    vector<int> v;
    for(auto i : operations){
        if(i[0] == 'I') {
            v.push_back(stoi(i.erase(0, 2)));
            sort(v.begin(), v.end());
        }
        else if(!v.empty()){
            if(i[2] == '1') v.pop_back();
            else v.erase(v.begin());
        }
    }
    
    if(!v.empty()){
        answer.push_back(v.back());
        answer.push_back(v.front());
    }
    else{
        answer.push_back(0);
        answer.push_back(0);
    }

    return answer;
}