[백준] 7662.cpp : 이중 우선순위 큐

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

#include <iostream>
#include <set>
using namespace std;

int t, k;
char func;

int main(void)
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> t;
    for(int tc = 0 ; tc < t ; tc++)
    {
        multiset<int> s;
        cin >> k;
        for(int i = 0, data ; i < k ; i++)
        {
            cin >> func >> data;
            if(func == 'I') s.insert(data);                 // 삽입 시 자동 오름차순 정렬
            else
            {
                if(s.empty())  continue;
                if(data == 1)  s.erase(--s.end());          // 뒤에서 하나 지움
                else           s.erase(s.begin());          // 앞에서 하나 지움
            }
        }
        if(s.empty()) cout << "EMPTY" << '\n';
        else cout << *(--s.end()) << " " << *(s.begin()) << '\n';
    }
}

 

[Approach]

1. 덱 사용해서 데이터 넣을때마다 정렬해주기

     -> 시간초과. k 가 백만개라서 어쩔 수 없는 거 같다.

2. 데이터 넣을 떄(I) 가 아니라 뽑아낼 때(D) 만 정렬을 해주기

     -> 역시나 시간 초과. 그냥 우선순위 큐를 두개 써서 해야겠다

3. 우선순위 큐를 오름차순 하나, 내림차순 하나 각각 만들어서 따로 처리해주기

     -> 시간초과는 안 나는 것 같은데 로직이 틀린 듯 하다. 왠지 empty 처리해주는 부분일 것 같은데..

4. 각각의 pop 연산들 수행 횟수와 전체 push 연산 수행 횟수를 비교해보면서 empty 처리를 해주기

5. pop 연산 할때마다 양쪽 큐를 서로 맞게 조정해주기

     -> 조정해줄때마다 임시로 큐 만들어서 저장해놓으니까 이번엔 메모리 초과다 ㅋㅋㅋㅋㅋㅋ 열받네 진짜

6. 우선순위 큐 말고 set 이나 map 을 사용하기

 

[Point]

1. set 도 자동정렬이 되는 컨테이너로, 반복자 사용해서 erase 가 가능하다는 것