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

문제

 

 

---

풀이

 

min-heap과 max-heap을 하나씩 만들어두고 각 정수별 인덱스도 함께 저장해서 삭제 여부를 체크하면 풀릴 것이다...

하지만 뭔가 이걸보니 지금까지 미뤄뒀던 set을 써야할 때가 왔구나 싶었다...

 

www.cplusplus.com/reference/set/set/?kw=set

set - C++ Reference

set은 입력되는 모든 값을 정렬된 상태(default : 오름차순)로 저장해주는 자료구조인데

그냥 set은 중복 저장이 불가능하고 multiset은 같은 값을 여러번 저장할 수 있다.

 

그럼 이 문제도 set에 저장하다가 최솟값은 첫번째 값, 최댓값은 마지막 값을 제거하면 되는데

내가 왜 set 사용을 망설였냐면 원소 접근 방식 때문이었다.

 

map이나 set이나 처음부터 원소를 접근하려면 vector처럼 v[0] 이렇게 접근하는게 아니라 iterator를 사용해야 한다.

이게 근데 또 포인터랑 관련된거라 어색해서 지금까지 쓰지 못했던 건데 이제 써봐야 한다...

---

소스코드

 

#include <iostream>
#include <set>

using namespace std;

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

    multiset<int> num; //중복 저장
    int T, k, n;
    char cmd;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> cmd >> n;
            if (cmd == 'I') //삽입
                num.insert(n);
            else if (!num.empty()) {
                if (n == 1) //최댓값 삭제
                    num.erase(--num.end());
                else //최솟값 삭제
                    num.erase(num.begin());
            }
        }
        if (num.empty()) //set이 비어있음
            cout << "EMPTY\n";
        else //최댓값, 최솟값 출력
            cout << *(--num.end()) << ' ' << *num.begin() << '\n';
        num.clear(); //set 초기화
    }
}

전체 소스코드다.

 

    multiset<int> num; //중복 저장

같은 값이 들어올 수 있다고 했으니 multiset을 사용한다.

 

        for (int j = 0; j < k; j++) {
            cin >> cmd >> n;
            if (cmd == 'I') //삽입
                num.insert(n);
            else if (!num.empty()) {
                if (n == 1) //최댓값 삭제
                    num.erase(--num.end());
                else //최솟값 삭제
                    num.erase(num.begin());
            }
        }

삽입 명령어가 들어오면 num.insert로 원소를 넣고

삭제 명령어가 들어오면 최댓값은 num.erase(--num.end())로, 최솟값은 num.erase(num.begin())으로 삭제한다.

왜 --num.end()냐면 num.end()는 마지막 원소의 다음을 가리키고 있다.

마치 우리가 for(int i=0;i<v.size();i++) 이렇게 i<v.size()일 때까지만 접근하는 것과 같은 원리다.

그래서 그 이전에 위치한 원소를 지워야 한다.

 

이 erase안에 그냥 key값이 들어오면 해당 key값에 해당하는 원소를 전부 지우고

iterator 값이 들어오면 우리가 보통 생각하는 인덱스 값을 지운다.

 

        if (num.empty()) //set이 비어있음
            cout << "EMPTY\n";
        else //최댓값, 최솟값 출력
            cout << *(--num.end()) << ' ' << *num.begin() << '\n';

iterator가 포인터니까 출력도 저렇게 해야 한다.

 

        num.clear(); //set 초기화

테스트 케이스가 여러개 들어오니 새로운 테스트 케이스 전 초기화 하자.