(프로그래머스) 이중우선순위큐

문제 링크

• 프로그래머스

요약

• 짱구굴리지말고 생각나는대로 풀면 된다.

최종 §

결과

• Heap 두개 써서 푸는 방법도 있던 것 같은데, 그냥 내부정렬되는 map/set 쓰는게 직관적이다.
• 아래처럼 multiset 을 쓰거나

#include <string>
#include <vector>
#include <set>
 
using namespace std;
 
vector<int> solution(vector<string> operations) {
	multiset<int> ms;
 
	for (auto &o : operations) {
		if (o == "D 1") {
			ms.erase(*ms.rbegin());
		} else if (o == "D -1") {
			ms.erase(*ms.begin());
		} else {
			ms.insert(stoi(o.substr(2)));
		}
	}
 
	if (ms.empty()) {
		return {0, 0};
	}
 
	return {*ms.rbegin(), *ms.begin()};
}

다른 방법 - map §

결과

코드

#include <string>
#include <vector>
#include <map>
 
#include <iostream>
 
using namespace std;
 
vector<int> solution(vector<string> operations) {
	map<int, int> tbl;
 
	for (auto &o : operations) {
		if (o == "D -1") {
			if (tbl.begin() != tbl.end()) {
				tbl.begin()->second--;
 
				if (!tbl.begin()->second) {
					tbl.erase(tbl.begin()->first);
				}
			}
		} else if (o == "D 1") {
			if (tbl.rbegin() != tbl.rend()) {
				tbl.rbegin()->second--;
 
				if (!tbl.rbegin()->second) {
					tbl.erase(tbl.rbegin()->first);
				}
			}
		} else {
			tbl[stoi(o.substr(2))]++;
		}
	}
 
	if (tbl.begin() == tbl.end()) {
		return {0, 0};
	}
 
	return {tbl.rbegin()->first, tbl.begin()->first};
}

• multiset 사용법이 생각안나면 그냥 map 으로 풀어도 된다.
  • 결과는 multiset 쓰는게 더 빠르고 메모리도 적게먹는 것 같긴 하다.