BOJ 7662 해설 C++

2021-11-05 212 words One minute

Table of Contents

접근 방법

두개의 우선순위 큐를 사용하는 풀이도 있지만, 우선순위 큐는 가장 위에 있는 값만 지울 수 있어 유연하지 못합니다. 그래서 이진 탐색 트리로 구현된 multiset을 사용하였습니다. C++의 multiset은 반복자를 활용해 삭제연산을 할 수 있습니다.

코드

 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
#include <bits/stdc++.h>

#define endl '\\n'

using namespace std;

#define SUBMIT
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

#ifndef SUBMIT
    (void)!freopen("input.txt", "r", stdin);
    cout << "# From the test case" << endl;
#endif

    int T; cin >> T;
    while(T--) {
        multiset<int> ms;

        int N; 
        cin >> N;

        char c;
        int value;
        for(int i = 0; i < N; ++i) {
            cin >> c >> value;

            if(c == 'I') {
                ms.insert(value);
                continue;
            } 

            if(c == 'D' && value == 1) {
                if(!ms.empty())
                    ms.erase(prev(ms.end()));

                continue;
            }

            if(c == 'D' && value == -1) {
                if(!ms.empty())
                    ms.erase(ms.begin());

                continue;
            }
        }

        if(ms.empty())
            cout << "EMPTY" << endl;
        else
            cout << *ms.rbegin() << ' ' << *ms.begin() << endl;

    }

    return 0;
}