7662 이중 우선순위 큐

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

문제

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

접근 방식

멀티셋

1. 최대값과 최소값에 접근하고 삭제할 수 있어야한다.
2. 삽입때마다 항상 정렬상태를 유지해야한다.
3. 처음엔 직접 클래스를 만들어서 벡터에 lower_bouund를 이용하여 입력을 받았었다. (시간초과)
4. 중복된 수가 나올 수 있으니 맵을 이용해볼까 하다가, 중복이 가능한 정렬상태 자료구조 -> 멀티셋이 생각났다.
5. 멀티셋으로 풀었더니 해결

문제 풀이

#include <iostream>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;

bool arr[21] = {};
int N, num;
string str;

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

    cin >> N;

    while (N-- > 0)
    {
        cin >> str;
        if (str == "add")
        {
            cin >> num;
            if (!arr[num])
                arr[num] = true;
        }
        else if (str == "check")
        {
            cin >> num;
            if (arr[num])
                cout << 1 << endl;
            else
                cout << 0 << endl;
        }
        else if (str == "remove")
        {
            cin >> num;
            if (arr[num])
                arr[num] = false;
        }
        else if (str == "toggle")
        {
            cin >> num;
            arr[num] = !arr[num];
        }
        else if (str == "all")
        {
            fill(arr, arr + 21, true);
        }
        else if (str == "empty")
        {
            fill(arr, arr + 21, false);
        }
    }


    return 0;
}

다시 생각해볼 점

1. 입력시 정렬상태 유지, 최소값과 최대값에 접근 및 삭제 가능 -> 이렇게 필요 조건을 정리해놓고
2. 멀티 셋 이라는 자료구조를 떠올리는게 중요한 부분이었던 것 같다.