[이중우선순위큐] - 우선순위큐 ★★★☆ / 복습 ○

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

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

---

[ 문제 접근 ]

 

그렇게 어렵지만은 않았던 문제.

 

나는 입력으로 주어진 operations 를 stringstream 객체를 이용해서 split 해줬다.

 

※ 주의 할 점은 stringstream 객체 ss 를 그냥 ss.str( ~~ ) 하고 해준다면 스트림 이 비워지지 않기 때문에

ss.clear()를 먼저 해주고 ss.str(operation[i]) 를 해준다.

 

우선순위큐를 마치 덱처럼 앞뒤에서 연산이 가능하게끔 해야하는 문제인데,

실제로 그렇게 못하니깐 우선순위 큐를 두개를 두어 그렇게 연산되는 것처럼 만들었따.

 

입력으로 주어진 명령어를 읽을때마다 알맞은 큐에서 작업하게끔!

 

---

[ 최종 코드 ]

 

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

using namespace std;

vector<int> solution(vector<string> operations) {
	vector<int> answer;
	std::priority_queue<int> max_heap;
	std::priority_queue<int,vector<int>,std::greater<int>> min_heap;

	std::stringstream ss;
	string order;
	string number;
	int cnt = 0;

	for (size_t i = 0; i < operations.size(); i++) {
		
		ss.clear();
		ss.str(operations[i]);
		ss >> order >> number;

		if (cnt == 0) {
			while (!min_heap.empty()) min_heap.pop();
			while (!max_heap.empty()) max_heap.pop();
		}


		if (order == "I") {
			max_heap.push(std::stoi(number));
			min_heap.push(std::stoi(number));
			cnt++;
		}
		else {
			if (cnt == 0) {
				continue;
			}
			if (stoi(number) > 0) {
				max_heap.pop();
				cnt--;
			}
			else {
				min_heap.pop();
				cnt--;
			}
		}
	}

	if (!cnt) {
		answer.push_back(0);
		answer.push_back(0);
	}
	else {
		int max = max_heap.top();
		int min = min_heap.top();
		answer.push_back(max);
		answer.push_back(min);
	}

	return answer;
}

 

 

 

---

[ Key Point ]

 

👉 opeartions 명령어에 따라 원소를 삭제하는 큐가 정해지기 때문에 큐를 전부 비워야함에도 남아 있는 원소가 있을 수 있다. 이 때, cnt 변수를 통해 큐 원소 개수를 추적하고 0이 될때 모든 큐를 비워준다.

	if (cnt == 0) {  // 어느 한 큐가 비었으면 모두 비우게끔.
			while (!min_heap.empty()) min_heap.pop();
			while (!max_heap.empty()) max_heap.pop();
	}

 

---

[ 다른 사람 풀이 ]

 

ref :: https://ssocoit.tistory.com/29

ref :: https://mjmjmj98.tistory.com/49