[백준] 7662 이중 우선순위 큐 (C++)

👉 문제 클릭

⚫ 문제

연산은 삭제를 뜻하는 D와 삽입을 뜻하는 I로 총 2개이다.
만약 I를 입력한다면 뒤이어 정수 n을 입력해준다. 이는 Q에 n을 삽입한다는 의미이다.
만약 D를 입력한다면 뒤이어 -1 또는 1을 입력해준다. 여기서 -1은 우선순위가 가장 낮은 것을 삭제한다는 의미이고, 1은 우선순위가 가장 높은 것을 삭제한다는 의미이다.

# input

T : 테스트케이스 개수
k : 연산의 개수
D or I and n : 연산

# output

모든 연산을 처리한 후 Q에 남아 있는 값 중 최댓값과 최솟값
만약 Q가 비어있다면 EMPTY

ex
EMPTY
333 -45

⚫ 문제해결

map은 자동으로 정렬되기 때문에 얠 이용했다.
우선순위가 낮을 경우엔 map.begin()을 높을 경우엔 map.end()를 이용하여
erase해주면 된다고 생각했다.

map은 key값이 중복될 수 없으므로, n이 열 번 들어와도 n은 하나. 삭제 한 번에 그냥 사라져버린다. 그래서 생각한 것은 개수를 따로 저장하는 것이다.

map<int, int> 형에
first에는 n
second에는 n의 개수를 넣어줬다!
n의 개수가 2이상이면 erase가 아닌 n--를 해주고,
n이 1개면 erase를 해주었다.

⚫ 소스코드

#include <iostream>
#include <vector>
#include <map>

using namespace std;

typedef long long ll;

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int T, N, n; cin >> T;
    char c;

    while (T--) {
        cin >> N;
        map<int, int> m;
        
        for (int i = 0; i < N; i++) {
            cin >> c >> n;
            if (c == 'I') {
                if (m.find(n) != m.end())
                    m[n]++;
                else
                    m.emplace(n, 1);
            }
            else if (c == 'D') {
                if (m.empty()) continue;

                if (n == 1) {
                    auto it = m.end();
                    it--;
                    if (it->second == 1)
                        m.erase(it);
                    else
                        it->second--;
                }
                else if(n == -1) {
                    if (m.begin()->second == 1)
                        m.erase(m.begin());
                    else m.begin()->second--;
                }
            }
        }

        if (m.empty()) cout << "EMPTY\n";
        else {
            auto it = m.end();
            it--;
            cout << it->first << " " << m.begin()->first<< "\n";
        }
    }

    return 0;
}