반응형

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

 

7662번: 이중 우선순위 큐

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

문제 난이도에 비해 생각을 좀 해야 하는 문제였습니다.

 

먼저 최댓값과 최솟값을 각각 저장할 maxpq와 minpq를 각각 만들고 입력받는 모든 수들을 넣습니다. 값을 넣을 때 map을 만들어 줘서 현재 그 숫자가 남아있는지 없는지를 체크합니다. 값을 뺄 때는 각각의 큐에서 빼지만 map과 비교하여 없는 숫자라면 계속 pop()해주고, 있는 숫자라면 map에서 빼고 난 후 pq에서 빼줍니다.

 

위 과정을 반복하면 현재 남아있는 숫자들이 map에 저장되어 있고, maxpq와 minpq를 모두 map과 비교하여 없는 숫자들을 pop해줍니다. 그러면 남은 숫자들이 pq에 각각 저장되어 있을 것이고 만약 큐 하나라도 비어있다면 EMPTY를 출력해주고 아니라면 각각의 pq에서 top을 출력해주면 됩니다.

 

[ 소스 코드 ]

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
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <queue>
#include <unordered_map>
 
using namespace std;
 
int main()
{
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        priority_queue<int> maxpq;        //최댓값 저장
        priority_queue<int, vector<int>, greater<int>> minpq;    //최솟값 저장
        unordered_map<int, int> m;        //현재 남아있는 숫자 저장
 
        int k;
        cin >> k;
        for (int i = 0; i < k; i++) {
            char ch;
            cin >> ch;
            if (ch == 'I') {
                int num;
                cin >> num;
                maxpq.push(num);
                minpq.push(num);
                m[num]++;
            }
            else {
                int num;
                cin >> num;
                if (num == -1) {
                    if (!minpq.empty()) {
                        while (m[minpq.top()] == 0) {    //없는 숫자가 남아있다면
                            minpq.pop();                //모두 pop
                            if (minpq.empty()) {
                                break;
                            }
                        }
                        if (!minpq.empty()) {
                            m[minpq.top()]--;
                            minpq.pop();
                        }
                    }
                }
                else {
                    if (!maxpq.empty()) {
                        while (m[maxpq.top()] == 0) {    //없는 숫자가 남아있다면
                            maxpq.pop();                //모두 pop
                            if (maxpq.empty()) {
                                break;
                            }
                        }
                        if (!maxpq.empty()) {
                            m[maxpq.top()]--;
                            maxpq.pop();
                        }
                    }
                }
            }
        }
 
        while (!maxpq.empty()) {        //없는 숫자 pop
            if (m[maxpq.top()] == 0) {
                maxpq.pop();
            }
            else {
                break;
            }
        }
 
        while (!minpq.empty()) {        //없는 숫자 pop
            if (m[minpq.top()] == 0) {
                minpq.pop();
            }
            else {
                break;
            }
        }
 
        if (maxpq.empty()) {
            cout << "EMPTY" << endl;
        }
        else {
            cout << maxpq.top() << " " << minpq.top() << endl;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14

+ Recent posts

티스토리툴바