7662번: 이중 우선순위 큐
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적
www.acmicpc.net
보통 PQ두개 써서 구현하겠지만
나는 Multiset을 써서 구현해봤다
삽입은 O(logN), 삭제는 amortized O(1)에 동작하므로
충분히 AC를 받기에 적합한 시간복잡도이다.
multiset::end()는 마지막 값보다 한칸 더 뒤에 있는 위치를 가리키므로
erase를 통해 지우려면 (--s.end())로 써줘야 정상적으로 지울 수 있다.
더보기
#include <bits/stdc++.h>
using namespace std;
multiset<int> s;
int main(){
cin.sync_with_stdio(false);
cin.tie(NULL);
int t,k;
int a;
char c;
cin >> t;
while(t--){
s.clear();
cin >> k;
while(k--){
cin >> c >> a;
if(c == 'I') s.insert(a);
if(c == 'D'){
if(!s.empty()){
if(a == 1) s.erase(--s.end());
if(a == -1) s.erase(s.begin());
}
}
}
if(s.empty()) cout << "EMPTY\n";
else cout << *(--s.end()) << " " << *(s.begin()) << "\n";
}
return 0;
}
반응형