C++で電話帳を設計する：セットとキューによる効率的な番号管理の実装

本記事では、次の3つの操作をサポートする電話帳（Phone Directory）クラスをC++で設計する方法を解説します。

• get ― まだ誰にも割り当てられていない番号を1つ取得する
• check ― 指定した番号が利用可能かどうかを確認する
• release ― 使用済みの番号を解放し、再利用できる状態に戻す

コンストラクタでは、あらかじめ最大 n 個の番号を初期化しておきます。

解法のアプローチ

この問題は、「使用中の番号を記録するセット」と「利用可能な番号を保持するキュー」という2つのデータ構造を組み合わせることで、効率的に解くことができます。キューによって番号を取得する順序が保証され、セットによって高速な存在チェックが可能になります。

具体的には、以下の手順に従います。

• 使用中の番号を管理するセット s を定義する
• 利用可能な番号を保持するキュー available を定義する
• コンストラクタは maxNumbers を受け取る
• N := maxNumbers とする
• i := 0 から i < N まで、i を1ずつ増やしながら繰り返す
  • i を available に挿入する

get() 関数

• available のサイズが 0 の場合は -1 を返す
• x := available の先頭要素とする
• x を s に挿入する
• available から先頭要素を取り出す
• x を返す

check(number) 関数

• number >= N または number < 0 の場合は false を返す
• number が s に存在しなければ true を返す

release(number) 関数

• check(number) が true の場合（＝すでに利用可能な番号の場合）は何もせず終了する
• x := number とする
• x を s から削除する
• x を available に挿入する

実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class PhoneDirectory {
public:
    set<int> s;
    queue<int> available;
    int N;
    PhoneDirectory(int maxNumbers){
        N = maxNumbers;
        for (int i = 0; i < N; i++) {
            available.push(i);
        }
    }
    int get(){
        if (available.size() == 0)
            return -1;
        int x = available.front();
        s.insert(x);
        available.pop();
        return x;
    }
    bool check(int number){
        if (number >= N || number < 0)
            return false;
        return s.find(number) == s.end();
    }
    void release(int number){
        if (check(number))
            return;
        int x = number;
        s.erase(x);
        available.push(x);
    }
};
main(){
    PhoneDirectory ob(3);
    cout << (ob.get()) << endl;
    cout << (ob.get()) << endl;
    cout << (ob.check(2)) << endl;
    cout << (ob.get()) << endl;
    cout << (ob.check(2)) << endl;
    ob.release(2);
    cout << (ob.check(2)) << endl;
}

入力

ob.get();
ob.get();
ob.check(2);
ob.get();
ob.check(2);
ob.release(2);
ob.check(2);

出力

0
1
1
2
0
1

出力の解説

このプログラムの動作を順に追ってみましょう。

1. 1回目の get() で番号 0 が割り当てられます。
2. 2回目の get() で番号 1 が割り当てられます。
3. check(2) は、番号 2 がまだ未使用のため true（1）を返します。
4. 3回目の get() で番号 2 が割り当てられます。
5. check(2) は、番号 2 が使用中になったため false（0）を返します。
6. release(2) によって番号 2 が解放されます。
7. check(2) は、再び true（1）を返します。

計算量

• get()：セットへの挿入がボトルネックとなり、O(log n)
• check()：セットの検索により、O(log n)
• release()：セットからの削除により、O(log n)
• 空間計算量：O(n)（n は最大番号数）