백준 7662번 이중 우선순위 큐

문제 링크입니다: https://www.acmicpc.net/problem/7662

최대 힙과 최소 힙을 priority_queue로 선언하여 풀면 되는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 집어넣을 때는 maxHeap과 minHeap 모두 똑같이 집어넣습니다.(집어 넣을 때 {입력 숫자, 인덱스})

2. 우선 유효하지 않은 숫자들을 모두 pop합니다.(다른 힙에서 pop된 숫자가 현재 힙의 top에 있을 수 있으므로)

3. 2번을 수행한 후 현재 힙의 top의 인덱스가 유효하지 않다고 표시하고 pop합니다.

4. 2와 3번을 N번 수행한 후 마지막으로 각각의 힙에 유효하지 않은 숫자들을 pop 시켜줍니다.

5. 4번을 수행한 뒤 힙이 비어있다면 EMPTY, 비어있지 않다면 각각의 top을 출력해줍니다.

6. 1 ~ 5번을 test_case만큼 진행합니다.

#include <iostream>

#include <queue>

#include <vector>

#include <algorithm>

#include <functional>

using namespace std;

 

const int MAX = 1000000 + 1;

 

int N;

bool visited[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int test_case;

        cin >> test_case;

 

        for (int t = 0; t < test_case; t++)

        {

                 cin >> N;

 

                 priority_queue<pair<int, int>> maxHeap;

                 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;

 

                 for (int i = 0; i < N; i++)

                 {

                         char op;

                         int num;

                         cin >> op >> num;

 

                         if (op == 'I')

                         {

                                 maxHeap.push({ num, i });

                                 minHeap.push({ num, i });

                                 visited[i] = true;

                         }

                         else

                         {

                                 if (num == 1)

                                 {

                                          //유효하지 않은 숫자들 전부 pop

                                          while (!maxHeap.empty() && !visited[maxHeap.top().second])

                                                  maxHeap.pop();

                                          if (!maxHeap.empty())

                                          {

                                                  //pop하므로 유효하지 않다고 표시

                                                  visited[maxHeap.top().second] = false;

                                                  maxHeap.pop();

                                          }

                                 }

                                 else

                                 {

                                          while (!minHeap.empty() && !visited[minHeap.top().second])

                                                  minHeap.pop();

                                          if (!minHeap.empty())

                                          {

                                                  visited[minHeap.top().second] = false;

                                                  minHeap.pop();

                                          }

                                 }

                         }

                 }

 

                 while (!maxHeap.empty() && !visited[maxHeap.top().second])

                         maxHeap.pop();

                 while (!minHeap.empty() && !visited[minHeap.top().second])

                         minHeap.pop();

 

                 if (minHeap.empty() && maxHeap.empty())

                         cout << "EMPTY\n";

                 else

                         cout << maxHeap.top().first << " " << minHeap.top().first << "\n";

        }

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~