[C/C++] 백준 7662번 - 이중 우선순위 큐

✏️  문제 링크

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

 

✏️ 문제 설명

✏️ 로직

이중 우선순위 큐라고 문제가 나와 있어서 priority_queue를 사용하려고 했지만 문제점 봉착

• 우선순위 큐에서는 마지막 값을 drop할 수가 없음

그렇다면 dequeue는?

• 양끝에서 값을 삽입하고 삭제가 가능
• 하지만 자동정렬을 제공하지 않음 ⇒ 값을 넣을 때마다 정렬을 해야 함

Map을 사용하자

• Map은 key값을 기준으로 오름차순 정렬
• map<long long, int>myMap 생성
• 값이 중복되어서 들어온다면 map에서 값을 기준으로 find를 해서 존재한다면 개수를 ++해주기, 없다면 그 냥 insert 해버리기

Multiset도 가능하다

• 값을 중복으로 삽입 가능
• 자동으로 오름차순 정렬

1. I면 정수 n을 큐에 삽입
2. D 1은 최댓값을 삭제(한 개만)
3. D -1은 최솟값을 삭제(하나만)
4. 마지막에서 최댓값만 최솟값, map이 비어있다면 empty를 출력

• 기타 2,3번의 과정에서 map이 비어있는지를 먼저 확인하기

✏️ 코드

#include<bits/stdc++.h>
using namespace std;

void fun(int k) {
    map<long long, int> myMap; // 기본적으로 오름차순 정렬
    char op;
    long long n;
    for (int i = 0; i < k; i++) {
        cin >> op >> n;
        if (op == 'I') {
            // 큐에 삽입하는 연산
            auto it = myMap.find(n);
            if (it == myMap.end()) {
                // 없다면
                myMap.insert({n, 1});
            } else {
                // 존재한다면 개수를 증가
                it->second++;
            }
        } else {
            if (n == -1) { // 큐애서 최솟값을 삭제하는 연산
                if (!myMap.empty()) { // 비어있지 않은 경우
                    auto it = myMap.begin();
                    if (it->second > 1) {
                        // 해당 최솟값이 2개 이상이라면 개수를 차감
                        it->second--;
                    } else {
                        // 1개라면 삭제
                        myMap.erase(it);
                    }
                }
            } else { // 큐에서 최댓값을 삭제하는 연산
                if (!myMap.empty()) { // 비어있지 않은 경우
                    auto it = myMap.rbegin();
                    if (it->second > 1) {
                        // 해당 최솟값이 2개 이상이라면 개수를 차감
                        it->second--;
                    } else {
                        // 1개라면 삭제
                        myMap.erase(prev(it.base()));
                    }
                }
            }
        }
    }

    if (myMap.empty()) {
        cout << "EMPTY"<<"\\n";
    }
    else {
        cout<<myMap.rbegin()->first<<" "<<myMap.begin()->first<<"\\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t, k;
    cin >> t;

    while (t--) {
        cin >> k;
        fun(k);
    }
}

#include<bits/stdc++.h>
using namespace std;

void fun(int k) {
    multiset<long long>s;
    char op;
    long long n;
    for (int i = 0; i < k; i++) {
        cin >> op >> n;
        if (op == 'I') {
            s.insert(n);
        } else {
            if (!s.empty()) {
                if (n==-1) s.erase(s.begin());
                else s.erase(prev(s.end()));
            }
        }
    }

    if (s.empty()) {
        cout << "EMPTY" << "\\n";
    } else {
        cout << *s.rbegin() << " " << *s.begin() << "\\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t, k;
    cin >> t;

    while (t--) {
        cin >> k;
        fun(k);
    }
}

✏️ 느낀 점

이건 골드4 문제이지만 알고리즘 구현보다는 자료구조를 얼마나 파악하고 있는지를 물어보는 것 같다. 문제를 보면서 어떤 자료구조를 사용해볼까? 라는 생각이 들었는데 map까지 떠올리는 과정은 좋았지만, 내가 생각보다 map의 내장 함수에 대해서 잘 모른다는 것을 느꼈다. 아무래도 iterator가 익숙하지 않은 것 같다. 이걸 계기로 자료구조에 대한 공부를 다시 해야겠다.

✏️ 결과

시간이 많이 걸린 것 같긴 한데, 기본적으로 제한 시간이 6초이고 1236ms면 문제의 조건에 비해서 널널하게 푼 것 같다. 그리고 Multiset보다는 Map이 더 빠르다. 아마도 Map을 사용할 때는 중복 값이 들어오면 추가적인 정렬 없이 value값을 증가시켰지만, Multiset에서는 중복 값이 들어오면 그거에 대해서 또 정렬을 해서 그런 것 같다.

• 중복된 값 처리의 효율성:
  • std::map은 키-값 쌍으로 데이터를 저장하므로, 중복된 값을 추가할 때 기존의 값에 대해 value(카운트)만 증가시키면 됩니다.
  • 이는 추가적인 정렬이나 노드 생성 없이 값의 카운트만 변경하므로, 중복된 값에 대해 추가적인 연산 비용이 들지 않습니다.
• 정렬 유지 비용 감소:
  • std::map은 내부적으로 Red-Black Tree를 사용하여 자동 정렬을 유지합니다.
  • 중복 값이 많을수록 std::map에서는 새로운 노드를 생성하지 않고 기존 노드의 카운트만 수정하므로 정렬 비용이 줄어듭니다.
• 삭제 연산의 효율성:
  • 삭제 연산에서 중복된 값의 개수를 줄일 때, std::map에서는 개수 값(value)을 감소시킵니다.
  • 반면, std::multiset은 실제로 해당 값을 찾아서 삭제하며, 삭제할 때도 정렬 상태를 유지해야 하므로 비용이 더 큽니다.

✏️ 시간복잡도

함수 설명 시간 복잡도

insert()	(키, 값) 쌍을 삽입. 키가 이미 존재하면 삽입되지 않음.	O(log n)
emplace()	insert와 비슷하지만, 생성자를 통해 직접 객체 삽입.	O(log n)
erase(key)	특정 키에 해당하는 요소를 삭제.	O(log n)
erase(iterator)	주어진 반복자가 가리키는 요소를 삭제.	O(log n)
find()	특정 키를 검색하고, 해당 키의 반복자를 반환.	O(log n)
count()	특정 키의 존재 여부를 반환(0 또는 1 반환).	O(log n)
operator[]	키를 기반으로 값을 검색하거나, 키가 없으면 삽입.	O(log n)
at()	특정 키의 값을 검색(예외를 던질 수 있음).	O(log n)
clear()	모든 요소를 삭제.	O(n)
size()	맵의 현재 요소 개수를 반환.	O(1)
empty()	맵이 비어 있는지 확인.	O(1)
begin() / end()	맵의 첫 번째 또는 마지막 반복자를 반환.	O(1)
rbegin() / rend()	역방향 첫 번째 또는 마지막 반복자를 반환.	O(1)
lower_bound()	주어진 키 이상인 첫 번째 요소의 반복자를 반환.	O(log n)
upper_bound()	주어진 키 초과인 첫 번째 요소의 반복자를 반환.	O(log n)
equal_range()	특정 키에 해당하는 범위를 반환.	O(log n)

이 표를 보았을 때, 계산을 해보면 시간복잡도는 (T*klogk)이 될 것 같다.