Pythonで解く「遠いバーコード」問題：隣接する要素が重複しないように並べ替えるアルゴリズム

問題の概要

倉庫に一列に並んだバーコードがあるとします。i番目のバーコードは barcodes[i] で表されます。このバーコードを並べ替えて、どの2つの隣接するバーコードも同じにならないようにするのが課題です。

例えば、入力が [1,1,1,2,2,2] の場合、出力は [2,1,2,1,2,1] のようになります。このように、同じ数字が隣り合わない配置を作ることができれば正解です。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• 辞書（マップ）d を作成する
• バーコード配列内の各数値の出現頻度を d に記録する
• 空のリスト x を用意する
• d のすべてのキーと値のペアを x に挿入する
• インデックス i を 0 で初期化する
• barcodes と同じ長さのリスト result を作成し、0 で埋める
• x を出現頻度に基づいてソートする
• i が result の長さ未満である間、以下を繰り返す
  • result[i] に x の最後のエントリの要素を代入する
  • x の最後のエントリの頻度を1減らす
  • 頻度が0になった場合、そのエントリを x から削除する
  • i を2ずつ増やす
• 次に i を 1 に設定し、同様の処理を奇数番目の位置に対して繰り返す
• 最後に result を返す

ポイントは、まず偶数番目の位置（0, 2, 4...）から頻度の高い要素を詰めていき、その後奇数番目の位置（1, 3, 5...）を埋めるという戦略です。これにより、最も出現回数の多い要素が隣り合うことを確実に防げます。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
   def rearrangeBarcodes(self, barcodes):
      d = {}
      for i in barcodes:
         if i not in d:
            d[i] = 1
         else:
            d[i]+=1
      x = []
      for a,b in d.items():
         x.append([a,b])
      i = 0
      result = [0]*len(barcodes)
      x = sorted(x,key=lambda v:v[1])
      while i <len(result):
         result[i] = x[-1][0]
         x[-1][1]-=1
         if x[-1][1]==0:
            x.pop()
         i+=2
      i=1
      while i <len(result):
         result[i] = x[-1][0]
         x[-1][1]-=1
         if x[-1][1]==0:
            x.pop()
         i+=2
      return result
ob = Solution()
print(ob.rearrangeBarcodes([1,1,1,2,2,2]))

入力

[1,1,1,2,2,2]

出力

[2, 1, 2, 1, 2, 1]

コードの解説

このアルゴリズムの計算量を確認しておきましょう。

• 時間計算量： O(n log n) — 出現頻度のソートに O(k log k)、要素の配置に O(n) かかります（k はユニークな要素数）。
• 空間計算量： O(n) — 頻度辞書と結果リストのための追加メモリが必要です。

頻度の高い要素から優先的に間隔を空けて配置することで、どのような入力に対しても「隣接する要素が重複しない」という条件を満たす並べ替えが保証されます。これは貪欲法（グリーディ法）の一種であり、シンプルながら非常に効果的な手法です。