C++でジグザグイテレータを実装する方法をわかりやすく解説

ジグザグイテレータとは？

2つの1次元配列が与えられたとき、それぞれの要素を交互に順番に返すイテレータを実装することを考えます。このイテレータには、次の2つのメソッドが必要です。

• next() — 次の要素を取得します。
• hasNext() — 次の要素がまだ存在するかどうかを判定します。

例えば、入力が v1 = [1,2]、v2 = [3,4,5,6] の場合、出力は [1,3,2,4,5,6] となります。つまり、v1 と v2 から交互に1つずつ要素を取り出し、片方が尽きた後は残りの配列の要素をそのまま返していきます。

解法のアプローチ：キューを使った実装

この問題は、キュー（queue）とペア（pair）を組み合わせることで、簡潔かつ効率的に解くことができます。ペアの第1要素には「配列内の現在位置（インデックス）」、第2要素には「どちらの配列かを示す識別子（0ならv1、1ならv2）」を格納します。

アルゴリズムの手順

1. ペアを格納するキュー q を定義します。
2. コンストラクタで2つの配列 v1 と v2 を受け取り、メンバ変数にコピーします。
3. v1 のサイズが0より大きい場合は、{0, 0} をキューに挿入します。
4. v2 のサイズが0より大きい場合は、{0, 1} をキューに挿入します。

next() メソッドの処理

1. ペア型の一時変数 temp を定義し、キューの先頭要素を取得してキューから削除します。
2. 戻り値用の変数 ret を0で初期化します。
3. temp.second が 1 の場合（v2側の要素）：
   • ret := v2[temp.first] として値を取得
   • temp.first を1増やす
   • temp.first が v2 のサイズ未満であれば、temp をキューに再度挿入
4. それ以外の場合（v1側の要素）：
   • ret := v1[temp.first] として値を取得
   • temp.first を1増やす
   • temp.first が v1 のサイズ未満であれば、temp をキューに再度挿入
5. ret を返します。

hasNext() メソッドの処理

キューが空でない場合に true を返します。これにより、まだ取り出せる要素が残っているかどうかを簡単に判定できます。

C++による実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class ZigzagIterator {
public:
    queue<pair<int, int>> q;
    vector<int> v1, v2;
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        this->v1 = v1;
        this->v2 = v2;
        if (v1.size()) {
            q.push({ 0, 0 });
        }
        if (v2.size()) {
            q.push({ 0, 1 });
        }
    }
    int next() {
        pair<int, int> temp;
        temp = q.front();
        q.pop();
        int ret = 0;
        if (temp.second == 1) {
            ret = v2[temp.first];
            temp.first++;
            if (temp.first < v2.size())
                q.push(temp);
        }
        else {
            ret = v1[temp.first];
            temp.first++;
            if (temp.first < v1.size())
                q.push(temp);
        }
        return ret;
    }
    bool hasNext() {
        return !q.empty();
    }
};
main(){
    vector<int> v1 = {1,3,5,7}, v2 = {2,4,6,8,10,12,17};
    ZigzagIterator ob(v1, v2);
    cout << (ob.next()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.hasNext() ? "True" : "False") << endl;
    cout << (ob.next()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.hasNext() ? "True" : "False") << endl;
    cout << (ob.next()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.hasNext() ? "True" : "False") << endl;
    cout << (ob.next()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.hasNext() ? "True" : "False") << endl;
}

入力

{1,3,5,7},{2,4,6,8,10,12,17}

出力

1
2
True
3
4
5
True
6
7
8
10
True
12
17
False

計算量の評価

• 時間計算量： next() および hasNext() の各呼び出しは O(1) で完了します。
• 空間計算量： キューには常に最大2つの要素しか保持されないため、追加の空間計算量は O(1) です（入力配列の保存分を除く）。

まとめ

ジグザグイテレータは、キューに「配列の識別子」と「現在のインデックス」のペアを管理させることで、2つの配列を交互に走査できます。この手法は、3つ以上の配列にも容易に拡張できる点が大きな魅力です。競技プログラミングやシステム設計の面接でも頻出のパターンなので、ぜひマスターしておきましょう。