✔ 문제 링크
✔ 문제해결전략
- Priority Queue
- Binary Search Tree(balanced)
✔ 해결과정
문제 이름이 이중 우선순위 큐니까 단순하게 생각해 보면 Max heap, Min heap으로 각각 최댓값, 최솟값 삭제를 처리하면 될 것 같다는 생각이 든다. 정답이다. Max, Min heap 2개를 들고 다니면서 삽입, 삭제를 처리해 주면 된다. 그런데 Max heap에서 최댓값을 삭제했으면 Min heap에서도 그 값을 삭제해 줘야 하는데 find의 시간 복잡도가 O(n)이다. Max, min 값을 O(log n)에 찾기 위해 heap을 사용하는 건데 이러면 heap을 사용할 이유가 없다. 결국 Max, min heap 간의 동기화가 쉽지 않다는 것이 문제인데 삽입하는 key에 flag를 달아줘서 어찌저찌 처리할 수 있을 것 같긴 하다.
그런데 이 문제에 더 잘 어울리는, 대소 관계가 잘 설정되는 자료구조가 있다. 바로 Binary Search Tree이다. 최솟값은 계속 왼쪽으로 타고 내려간 값이고, 최댓값은 계속 오른쪽으로 타고 내려간 값이다. 따라서 balanced 되어 있다는 가정하에 두 연산 모두 O(log n)에 처리할 수 있다. 이 문제에서는 key-value 쌍 형태의 데이터를 처리하는 것이 아니고 중복된 key 값이 들어올 수 있으므로 std::multiset을 사용하면 된다.
✔ 정답 CODE(std::multiset)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) {
int k;
cin >> k;
multiset<int> ms;
while(k--) {
char input;
int n;
cin >> input;
if(input == 'I') {
cin >> n;
ms.insert(n);
}
else if(input == 'D') {
cin >> n;
if(n == 1) ms.erase(prev(ms.end()));
else if(n==-1) ms.erase(ms.begin());
}
} // while k
if(ms.empty()) cout << "EMPTY" << '\n';
else cout << *ms.begin() << " " << *prev(ms.end());
} // while t
}
✔ 정답 CODE(Max, Min heap) - 추가예정
✔ Check Point
"만약 Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시해도 좋다."라고 나와 있어서 이런 케이스는 무시하고 풀라는 것으로 이해했는데 출력 결과가 계속 이상하게 나왔다. 그래서 다시 test case를 유심히 보니 2개를 삽입하고 3번 연달아 삭제하는 경우가 있었다.
따라서 multiset이 empty인데 erase를 시도하는 경우를 처리해 주어야 한다.
또한 end 메소드가 마지막 원소의 한 칸 뒤를 가리킨다는 것을 명심해야 한다. 따라서 최댓값을 지울 때에는 ms.erase(ms.end())가 아니라(이렇게 쓰면 past the end iterator 뜬다) ms.erase(prev(ms.end()))이다.
마지막으로 multiset에서 erase 메소드가 인자로 전달된 key 값을 모두 지운다는 것을 명심해야 한다. 따라서 ms.erase(*prev(ms.end()) 이런 식으로 적으면 최댓값이 여러 개일 경우 싹 다 erase 된다.
✔ std::iterator end 및 prev, next, advance
- end: 마지막 원소의 한 칸 뒤를 가리킨다
- prev: 기준 iter에서 -n차 iter 반환
- next: 기준 iter에서 +n차 iter 반환
- advance: 기준 iter를 인자로 들어온 iter로 변경해준다
✔ Comment
내일 제주도로 훈련 가서 토요일 새벽에 돌아옵니다,, 안녕,,
와 제주도 여행 부럽다...