Pythonでエンコーディングが一意のバイナリ文字列を表すかどうかを確認する方法

問題の概要

サイズkのバイナリ文字列のエンコーディングを表す配列numsが与えられたとします。このとき、指定されたエンコーディングが一意にバイナリ文字列を特定できるかどうかを確認する必要があります。ここでいうエンコーディングとは、「連続する1の個数」を要素とし、それぞれのブロックが単一の0で区切られている形式を指します。

例えば、入力がnums = [4, 2, 3]、k = 11の場合を考えてみましょう。このエンコーディングは「4個の1」「0」「2個の1」「0」「3個の1」という並びを意味します。つまり、対応するバイナリ文字列は「11110110111」となり、その長さはちょうど11(k)です。したがって、出力はTrueになります。

解法のアプローチ

この問題は、非常にシンプルな計算で解決できます。以下の手順に従います。

• total := numsの全要素の合計を求める
• total := total + (numsのサイズ − 1) を計算する(区切りとなる0の個数を加算)
• totalがkと等しければtrueを返し、そうでなければfalseを返す

ポイントは、0の個数が常に「要素数 − 1」になるという点です。各ブロック(連続する1のグループ)は必ず1つの0で区切られるため、文字列全体の長さは「1の総数 + 0の総数」で一意に求まります。この合計がkと一致すれば、そのエンコーディングは長さkのバイナリ文字列を一意に表していることになります。

実装例

以下のコードで、より理解を深めましょう。

def solve(nums, k):
    total = sum(nums)
    total += len(nums) - 1
    return total == k

nums = [4, 2, 3]
k = 11
print(solve(nums, k))

入力

[4, 2, 3], 11

出力

True

計算量について

このアルゴリズムの時間計算量はO(n)(nは配列numsの長さ)、空間計算量はO(1)です。sum()関数で配列を一度走査するだけで判定が完了するため、非常に効率的な解法と言えます。