[자료 구조] 멀티셋 C++

개요

C++에서의 멀티셋은 STL에서 제공하는 연관 컨테이너로, 중복된 키 값을 허용하는 특징이 있다.

주요 특징은 하기와 같다.

• 자동 정렬: 원소들이 자동으로 정렬됨
• 중복 허용: 같은 값을 여러 번 저장 가능
• 검색 효율: 이진 탐색 트리 기반으로 구현되어 있어 검색이 효율적 (O(log n))
• 불변성: 한번 삽입된 원소의 값을 직접 수정할 수 없음

멀티셋은 중복된 데이터를 유지하면서 정렬이 필요한 경우에 유용하다.

예를 들어 빈도수 계산, 정렬된 데이터에서 중복을 허용하는 경우, 우선순위가 같은 항목들을 관리할 때이다.

 

구조체를 통한 operator함수 또한 적용이 가능하다.

삼성 SW 역량평가 B형을 준비할 때 기출문제를 풀며 얻었던 지식에 관해 짧게 작성해 보겠다.

 

 

멀티셋을 이용한 데이터 관리

#include<iostream>
#include<set>
#include<vector>
using namespace std;
struct Prio {
    int Id, Ab;
    bool operator<(const Prio& other) const {
        if (Ab == other.Ab) return Id < other.Id;
        return Ab > other.Ab;
    }
};

struct League {
    multiset<Prio> more, less;

    void valance() {
        while (more.size() < less.size()) {
            Prio prio = *--less.end();
            less.erase(prio);
            more.insert(prio);
        }

        while (less.size() < more.size() - 1) {
            Prio prio = *more.begin();
            more.erase(prio);
            less.insert(prio);
        }
    }

    void input(Prio p) {
        if (more.empty()) {
            more.insert(p);
            return;
        }
        else {
            if (p < *more.begin()) less.insert(p);
            else more.insert(p);
        }
        valance();
    }

    Prio output() {
        if (more.size() == less.size()) return *--less.end();
        else return *more.begin();
    }

    void del(Prio p) {
        if (more.count(p)) more.erase(p);
        else less.erase(p);
        valance();
    }
};

 

위 내용은 set처럼 begin(), rbegin(), end() 등과 같이 이터레이터를 통해 데이터를 관리하는 자료구조에서

중간값의 데이터를 LogN의 시간 복잡도로 찾을 수 있도록 도와주는 구조체를 정의했다.

 

Prio 구조체는 인덱스 idx와 값 val을 정의한다.

비교 함수는 val이 큰 값을 기준으로 정렬하고, val이 동일한 경우 idx가 작은 값을 기준으로 정렬한다.

 

League구조체는 Prio타입의 멀티셋 less, more을 가지고 있다.

여기서 less는 값이 작은 부분을, more은 값이 큰 부분을 중복이 가능한 집합 형태이다.

 

구조체 함수인 valance를 통해 less와 more함수의 크기를 조정해 준다.

만약 more의 크기가 less의 크기보다 작다면 prio의 맨 끝의 요소를 less에서 지우고 more에 삽입해 준다.

만약 less의 크기가 more의 크기에서 1을 뺀 값보다 작다면 more의 시작 요소를 more에서 지우고 less에 삽입해 준다.

 

구조체 함수인 input을 통해 요소를 삽입해 줄 수 있다.

Prio타입의 변수 p가 입력되면, more이 비었을 경우 우선적으로 more에 값을 삽입해 준다.

만약 more이 비지 않았다면 p와 more의 첫번째 값과 비교해 더 작다면 less로, 아니라면 more에 삽입해 준다.

삽입 작업이 종료된 경우 valance 함수를 호출해 준다.

 

구조체 함수인 output을 통해 중간값을 찾아 리턴해 줄 수 있다.

만약 more과 less의 크기가 크다면 less의 끝에 있는 요소를 찾아서 반환해 준다.

그게 아니라면 more의 크기가 더 큰 경우이므로 more의 끝에 있는 요소를 찾아서 반환해 준다.

 

구조체 함수인 del을 통해 특정 값을 삭제해 줄 수 있다.

Prio타입의 변수 p가 입력되면, 우선 count메서드를 통해 more에 해당 값이 존재하는지 체크해 준다.

존재한다면 해당 값을 erase메서드를 통해 삭제하고, 존재하지 않는다면 less에서 찾아 해당 값을 찾아 삭제한다.

삭제 작업이 종료된 경우 valance 함수를 호출해 준다.

 

이를 통해 특정 값을 찾기 위해 이터레이터를 옮겨가며 선형 탐색으로 중간값을 찾을 필요 없이, 두 개의 멀티셋을 활용하여 LogN의 시간 복잡도로 중간값을 찾을 수 있게 된다.