백준 문제

백준 7662 (이중 우선순위 큐) c++

kangyuseok 2022. 8. 16. 00:03
728x90

문제

 

7662번: 이중 우선순위 큐

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적

www.acmicpc.net

명령문을 입력 받습니다.

예를 들어 

I 60 이면 벡터에 60을 삽입합니다.

D -1 이면 벡터 값 중에 최솟값을 삭제합니다.

D 1 이면 벡터 값 중에서 최댓값을 삭제합니다. 

k개의 명령문이 끝나고 남아있는 벡터의 최댓값과 최솟값을 출력하면 되는 문제입니다.

만약 벡터가 비어있으면 "EMPTY"를 출력하면 됩니다.

 

처음에 생각한 방안은 priority queue를 오름차순과 내림차순으로 두가지의 큐를 관리해

D 명령어를 처리하는 방식입니다.

하지만 이렇게 되면 오름차순에서 삭제된 원소가 내림차순에 존재하게 됩니다. 반대도 마찬가지 입니다.

따라서 추가적인 장치가 필요합니다.

바로 MAP을 이용하는 것입니다. 

 

문제에서 삽입되는 원소들은 중복으로 주어질 수 있으니까 MAP을 <int, int>로 선언해 

만약  "I 58" 이라는 명령어가 들어오면 <58, 1> 로 삽입해 주고 또 58이 들어오면 MAP[58]++하게 해주면 됩니다.

즉, MAP을 이용해 삽입된 원소와 삭제된 원소를 체크해주고 D 명령문이 들어올 때마다 정리해주면 됩니다.

전체 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        map<int, int>m;
        priority_queue<int>up;
        priority_queue<int, vector<int>, greater<int>>down;
        vector<int>v;
        int k;
        cin >> k;
        for (int i = 0; i < k; i++) {
            char c;
            cin >> c;
            if (c == 'I') {
                int a;
                cin >> a;
                up.push(a);
                down.push(a);
                if (m.count(a) == 0)
                    m[a] = 1;
                else
                    m[a]++;
            }
            else {
                int a;
                cin >> a;
                if (a == -1 && !down.empty()) {
                    if (!m[down.top()]) 
                        while (!down.empty() &&!m[down.top()])down.pop();
                    if (!down.empty()) {
                        m[down.top()]--;
                        down.pop();
                    }
                }
                else if (a == 1 && !up.empty()) {
                    if (!m[up.top()])
                        while (!up.empty()&&!m[up.top()])up.pop();
                    if (!up.empty()) {
                        m[up.top()]--;
                        up.pop();
                    }
                }
            }
        }
        if (!up.empty())while (!up.empty() && !m[up.top()])up.pop();
        if (!down.empty())while (!down.empty()&&!m[down.top()])down.pop();
 
        if (up.empty() && down.empty()) cout << "EMPTY" << '\n';
        else cout << up.top() << ' ' << down.top() << '\n';
 
    }
    
 
    return 0;
}
 
cs