[Algorithm] Baekjoon 7662번 : 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 0;
    int operationCount = 0;
    char operation;
    int num;
    vector<string> results;
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> operationCount;
         
        multiset<int> ms;
 
        for (int j = 0; j < operationCount; j++)
        {
            cin >> operation >> num;
 
            if (operation == 'I')
            {
                ms.insert(num);
            }
            else // if Delete
            {
                if (ms.size() > 0)
                {
                    if (num == 1)
                    {
                        ms.erase(--ms.end());
                    }
                    else
                    {
                        ms.erase(ms.begin());
                    }
                }
            }
        }
 
        if (ms.size() == 0) results.push_back("EMPTY");
        else
        {
            string temp = "";
            temp += to_string(*(--ms.end()));
            temp += ' ';
            temp += to_string(*ms.begin());
            results.push_back(temp);
        }
    } // 테스트케이스끝.
 
    for (auto& temp : results)
    {
        cout << temp << endl;
    }
 
    return 0;
}

동일한 문제를 프로그래머스에서 풀었었다.

좀 예전이라, 백준에서 다시 풀어보려하니 생각보다 쉽게 풀지는 못했다.

그러다가 특정반례에서 해결이 안되서 프로그래머스에서 제출했던 코드를 봤더니 백준에서 작성한 코드랑 로직이 동일했다.

그렇기 때문에 프로그래머스에서 통과한 코드여도 백준에선 통과가 안됐다;; 프로그래머스쪽에서 테스트케이스가 너무 적은것같다

어쨌든 좀 더 쉽게 푸는 방법 없을까해서 다른 사람은 어떤식으로 풀었나 봤더니 multiset을 사용하길래 조금 알아봤더니 iter로 관리가능한 자동정렬 컨테이너라는 것을 알고 바로 문제를 해결할 수 있었다.

우선순위큐처럼 내부는 자동정렬이니, 그저 앞뒤를 erase해주면 된다. 

물론 begin()을 erase하면 뒤의것을 다 땡겨와야하기 때문에 성능이 좋지 않지만, 끝요소를 erase하는거는 성능이 괜찮기 때문에 통과하는 것 같다.