백준 7662 이중 우선순위 큐 c++ [컴공과고씨]

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

내가 처음 푼 방법은 우선순위 큐 한개와 스택을 이용해서 풀었다.

최대값은 top에서 그냥 빼주면 끝이지만 최소값을 빼는 방법은 스택을 이용해서 큐에 있는 모든 수를 빼면서 스택에 넣어준다. 그럼 스택 맨 위에 있는 것은 최소값이 된다. 그래서 스택에서 맨 위 값을 제거하고 다시 우선순위 큐에 넣는 방식으로 구현했다. 결과는 시간초과이다.

그래서 다른 방법 multiset을 이용하는 방법으로 풀었다.

 

multiset의 기본 설명과 사용법은 https://hagisilecoding.tistory.com/61 여기서 간단히 보고 오면 이해할 수 있다.

multiset은 삽입시 정렬해서 삽입을 하기 때문에 최대값을 지울때는 맨뒤에서 하나 지우고 최소값을 지울때는 맨 앞에서 하나 지우는 방식으로 구현해주었다.

 

단계별 풀이

1. multiset q선언

2. q.insert로 삽입

3. iterator를 이용해서 맨뒤의 최대값 삭제 구현

4. iterator를 이용해서 맨앞 최소값 삭제 구현

5. set이 비어있지 않으면 multiset에 남아있는 맨 앞부분과 맨 뒷 부분 출력

 

전체코드

#include <iostream>
#include <set>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    char c;
    int T, k, n;
    cin >> T;
    while(T--){
        cin >> k;
        multiset<int> q; // multiset 오름차순 정렬
        for (int i = 0; i < k;i++){
            cin >> c >> n;
            if(c =='I'){
                q.insert(n); // 삽입
            }else if(c == 'D'){
                if(q.empty()){
                    continue;
                }else if(n == 1){ // 최대값 제거시
                    auto iter = q.end(); // 맨 끝값 +1 
                    iter--; // 맨 끝값으로 이동
                    q.erase(iter); // 최대값 삭제
                }else if(n == -1){
                    q.erase(q.begin()); // 최소값 삭제
                }
            }
        }
        if(q.empty()){
            cout << "EMPTY" << '\n';
        }else {   
            auto iter = q.end();
            iter--;
            cout << *iter << " " << *q.begin() << '\n';
        }
    }
    return 0;
}
 

체감난이도	걸린시간	참고	사용 알고리즘, 문법
중	30min	시간초과를 걸린 후 multiset를 사용해야한다는 힌트를 보고 multiset에 대해 공부 후 문제를 품.	multiset