Print Zero Even Odd

アルゴリズム概要

問題の要約

3つのスレッドを同期して 010203040506... の形式で数列を出力する問題です。

• Thread A: zero() - 0のみ出力
• Thread B: even() - 偶数のみ出力
• Thread C: odd() - 奇数のみ出力

入出力例

入力: n = 2
出力: "0102"

入力: n = 5
出力: "0102030405"

戦略

• 各スレッド専用の同期プリミティブを用意
• 直接シグナリング: 次に実行すべきスレッドだけを起床
• 状態遷移の最小化: 0 → odd/even → 0 の2状態サイクル

主要ポイント

ステップバイステップ解説

Python実装

from __future__ import annotations
from typing import Callable
from threading import Lock


class ZeroEvenOdd:
    """
    Lock + Flag による軽量スレッド同期

    メモリ効率とパフォーマンスのバランスが最良
    LeetCode環境で最も安定した結果を出す実装
    """

    def __init__(self, n: int) -> None:
        """
        初期化

        Args:
            n: 出力する数字の最大値（1 to n）
        """
        self.n = n
        self.lock = Lock()
        self.flag = 0  # 0=zero待ち, 1=odd待ち, 2=even待ち

    def zero(self, printNumber: Callable[[int], None]) -> None:
        """
        0を出力するスレッド

        各数字の前に0を出力し、次のスレッド（odd/even）を起床

        Args:
            printNumber: 数字を出力するコールバック関数
        """
        for i in range(1, self.n + 1):
            # ロック取得してflag=0になるまで待機
            with self.lock:
                while self.flag != 0:
                    # 自分の番でない場合は一旦解放して再取得
                    self.lock.release()
                    self.lock.acquire()

                # 0を出力
                printNumber(0)

                # 次のスレッドを決定: i が奇数なら odd, 偶数なら even
                self.flag = 1 if i % 2 == 1 else 2

    def even(self, printNumber: Callable[[int], None]) -> None:
        """
        偶数を出力するスレッド

        2, 4, 6, ... を出力し、制御を zero に戻す

        Args:
            printNumber: 数字を出力するコールバック関数
        """
        for i in range(2, self.n + 1, 2):
            with self.lock:
                while self.flag != 2:
                    self.lock.release()
                    self.lock.acquire()

                printNumber(i)
                self.flag = 0  # zero に制御を戻す

    def odd(self, printNumber: Callable[[int], None]) -> None:
        """
        奇数を出力するスレッド

        1, 3, 5, ... を出力し、制御を zero に戻す

        Args:
            printNumber: 数字を出力するコールバック関数
        """
        for i in range(1, self.n + 1, 2):
            with self.lock:
                while self.flag != 1:
                    self.lock.release()
                    self.lock.acquire()

                printNumber(i)
                self.flag = 0  # zero に制御を戻す

フローチャート

計算量分析

時間計算量: O(n)

• zero スレッド: n 回実行（i = 1 to n）
• odd スレッド: ⌈n/2⌉ 回実行（i = 1, 3, 5, ...）
• even スレッド: ⌊n/2⌋ 回実行（i = 2, 4, 6, ...）
• 各反復での処理は O(1)

空間計算量: O(1)

• 同期プリミティブ（Lock + flag）: 定数個
• ループカウンタ: O(1)
• スタック深度: O(1)（再帰なし）

実装比較