Programmers > 코딩테스트 연습 > 힙 > 이중우선순위큐

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

풀이

필요할 때마다 어쩔 때는 앞에서, 어쩔 때는 뒤에서 숫자를 꺼내야 하므로

deque라는 자료구조를 사용한다.

쉽게 생각해서 deque은 앞뒤로 뚫려있는 큐의 형태라고 생각하면 된다.

여기서 우선순위를 구현하기 위해 먼저 새로운 숫자를 맨 앞에 집어넣은뒤

bubble sort를 할 때 처럼 오름차순이 될 때 까지 새로 들어간 숫자를 뒤로 밀어주면서

조건을 만족시키도록 하였다.

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

using namespace std;

vector<int> solution(vector<string> arguments) {
	vector<int> answer;
	deque<int> deq;

	for (int i = 0; i < arguments.size(); i++) {
		string s = arguments[i];
		int num = stoi(s.substr(2));
		if (s.substr(0, 1) == "I") {
			deq.push_front(num);
			if (deq.size() > 1) {
				for (int i = 0; i < deq.size()-1; i++) {
					if (deq[i] > deq[i + 1]) swap(deq[i], deq[i + 1]);
					else break;
				}
			}
		}
		else {
			if (!deq.empty()) {
				if (num == 1) deq.pop_back();
				else deq.pop_front();
			}
		}
	}
	if (deq.empty()) {
		answer.push_back(0);
		answer.push_back(0);
	}
	else {
		answer.push_back(deq.back());
		answer.push_back(deq.front());
	}
	return answer;
}