(c++)프로그래머스 코딩테스트 연습 - 이중우선순위큐

programmers.co.kr/learn/courses/30/lessons/42628

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

[풀이]

큐의 양쪽에서 삽입, 삭제 연산을 해야하므로 deque를 사용하여 구현하였다.

삽입을 할 때마다 큐를 정렬하는 과정이 필요하다.

 

#include <string>
#include <vector>
#include <deque>
#include <algorithm>//sort

using namespace std;

vector<int> solution(vector<string> operations) {
	vector<int> answer;
	deque<int>q;
	for (int i = 0; i < operations.size(); i++) {
		char OP = operations[i].at(0);
		int num = stoi(operations[i].substr(2));
		//숫자 삽입
		if (OP == 'I') {
			q.push_back(num);
			sort(q.begin(), q.end());
		}
		//최솟값 삭제
		else if (num == -1) {
			if (!q.empty())
				q.pop_front();
		}
		//최댓값 삭제
		else {
			if (!q.empty())
				q.pop_back();
		}
	}
	if (q.empty()) {
		answer.push_back(0);
		answer.push_back(0);
	}
	else {
		answer.push_back(q.back());
		answer.push_back(q.front());
	}
	return answer;
}