[C++] 7662번 이중 우선순위 큐 - 우선순위 큐, 트리

결과적으론 나는 이 문제를 푸는 데 실패하였고 더 이상 C언어로 알고리즘 코드를 짜는 것은 힘들다고 생각하였다. 그래서 C언어에서 C++언어로 바꾸기로 하였고 코드는 다른 사람의 블로그에서 가져왔다. 그대로 가져왔고 내가 짠 코드는 절대 아니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

priority_queue<int, vector<int>, greater<int>> min_pq;
priority_queue<int, vector<int>, less<int>> max_pq;
map<int, int> dict;

int T, k, n;
char c;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> T;
    
    while (T) {
        while (!min_pq.empty()) {min_pq.pop();}
        while (!max_pq.empty()) {max_pq.pop();}
        dict.clear();
        
        cin >> k;
        
        for (int i=0; i<k; i++) {
            cin >> c >> n;
            
            if (c=='I') {
                min_pq.push(n);
                max_pq.push(n);
                
                if (!dict.count(n))
                    dict[n]=1;
                else
                    dict[n]++;
            }
            else {
                if (n==1) {
                    while (!max_pq.empty() && !dict[max_pq.top()])
                        max_pq.pop();
                    if (!max_pq.empty()) {
                        dict[max_pq.top()]--;
                        max_pq.pop();
                    }
                }
                else {
                    while (!min_pq.empty() && !dict[min_pq.top()])
                        min_pq.pop();
                    if (!min_pq.empty()) {
                        dict[min_pq.top()]--;
                        min_pq.pop();
                    }
                }
            }
        }
        
        while (!max_pq.empty() && !dict[max_pq.top()])
            max_pq.pop();
        while (!min_pq.empty() && !dict[min_pq.top()])
            min_pq.pop();
        
        if (max_pq.empty() || min_pq.empty())
            cout << "EMPTY\n";
        else
            cout << max_pq.top() << " " << min_pq.top() << "\n";
        
        T--;
    }
    
    return 0;
}

 

 

나는 C++언어를 접한 것이 이번이 처음이기 때문에 이 코드를 이해하는데 상당히 많은 시간을 썼다. 링크는 아래에 있다.

 

 

<코드 출처>

https://please-amend.tistory.com/entry/%EB%B0%B1%EC%A4%80-7662%EB%B2%88-%EC%9D%B4%EC%A4%91-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-Ccpp-%ED%92%80%EC%9D%B4

백준 7662번 이중 우선순위 큐 - C++(cpp) 풀이

 

<switch문 컴파일 에러>

https://blankspace-dev.tistory.com/386

[C++] switch case문 jump to case label 오류 문제 해결 방법

 

<C++ 큐>

https://life-with-coding.tistory.com/408

[C++][STL] Queue 기본 사용법 및 예제

 

<C++ 벡터>

https://blockdmask.tistory.com/70

[C++] vector container 정리 및 사용법

 

<C++ greater, less>

https://xzio.tistory.com/272

[STL] less, greater, plus, minus 예제

 

<C++ map>

https://life-with-coding.tistory.com/305

[C++][STL] map 사용법 정리

 

<ios_base::sync_with_stdio>

https://modoocode.com/281

C++ 레퍼런스 - ios_base::sync_with_stdio 함수

 

<C++ cin, cout>

https://coding-factory.tistory.com/479

[C++] 입력문 / 출력문 (cin, cout) 사용법 & 예제

 

<cin.tie(NULL)>

https://ip99202.github.io/posts/%EC%9E%85%EC%B6%9C%EB%A0%A5-%EC%86%8D%EB%8F%84-%EC%A4%84%EC%9D%B4%EA%B8%B0/

sync_with_stdio(false) cin.tie(NULL) cout.tie(NULL)

 

<C++ auto>

https://dydtjr1128.github.io/cpp/2019/06/04/Cpp-auto.html

C++ auto란? - dydtjr1128's Blog

 

<C++ priority_queue>

https://kbj96.tistory.com/15

[C++ STL] Priority_queue 사용법

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.