[BaekJoon/백준] 7662번 C++

 

처음에는 우선순위 큐(priority_queue) 두개를 사용해서 문제를 풀어보려 시도했다.

근데 단순히 두 개만 이용할 것도 아니고, 이미 삭제된 노드에 대해서도 서로 체크해줘야 하는 어려움이 있었다.

나는 결국 우선순위 큐 두개를 사용해서 풀진 못했지만 그런 방법도 있다!

velog.io/@leehj8896/백준-7662번-이중-우선순위-큐

 

 

검색을 하다가, STL <set> 에 있는 multiset 자료구조를 알게 되었다.

이 자료구조는 이름에 맞게, 중복도 허용해주지만

알아서 정렬을 시켜준다는 점이 크게 매력적이였다.

 

이 자료구조를 이용하면 이 문제를 엄청나게 간단하게 풀 수 있었다.

#include <iostream>
#include <set>

using namespace std;

int T, N, input;


int main() {
        
    ios::sync_with_stdio();
    cin.tie(NULL);
        
    string command;

    cin >> T;
    
    while(T--) {
        
        cin >> N;
        
        multiset<int> ms;
        
        while(N--) {
            
            cin >> command;
            
            if(command == "I") {
                cin >> input;
                ms.insert(input);
            } else if(command == "D") {
                cin >> input;
                
                if(ms.empty())
                    continue; // 무시

                if(input == 1) {
                    // end 는 마지막 노드 다음을 가리키고 있다.
                    multiset<int>::iterator it =  ms.end();
                    it--;
                    ms.erase(it);
                } else if(input == -1) {
                    ms.erase(ms.begin());
                }
            }
            
        }
        
        if(ms.empty())
            cout << "EMPTY\n";
        else {
            // end 는 마지막 노드 다음을 가리키고 있다.
            multiset<int>::iterator it =  ms.end();
            it--;
            cout << *(it) << " " << *(ms.begin()) << '\n';
        }
        
    }
}

관련 자료는 아래 블로그에 잘 정리되어 있어서 참고하면 좋을 것 같다!

sorious77.tistory.com/113