Pythonで重複するディレクトリ名を一意にするプログラムの実装方法

問題概要

n個の文字列からなる配列 names が与えられたとします。ファイルシステム上にn個のディレクトリを作成し、i番目の時点で names[i] という名前のディレクトリを作成していきます。同じ名前のファイルは存在できないため、重複するディレクトリ名を登録しようとした場合、システムは自動的に「(k)」という形式の接尾辞を追加します。ここで k は、その名前が一意になるような最小の正の整数です。求めるのは長さnの文字列配列であり、ans[i] は i 番目のディレクトリを作成した際に実際に割り当てられる名前になります。

例えば、入力が names = ["my_dir","my_dir(1)","my_new_dir","my_new_dir","abc"] の場合、出力は ['my_dir', 'my_dir(1)', 'my_new_dir', 'my_new_dir(1)', 'abc'] となります。「my_new_dir」はすでに一度使用されているため、2つ目の同名ディレクトリには「(1)」が付けられるからです。

解決手順

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

• dic：キーが存在しない場合は0を返す新しいマップ（defaultdict）を作成します。
• res：結果を格納するための新しいリストを作成します。
• names 内の各 name について、次の処理を行います。
  • name が dic に存在しない場合：
    • dic[name] を +1 します。
    • res の末尾に name を追加します。
  • それ以外の場合：
    • newname := name + '(' + dic[name] + ')' という候補名を作成します。
    • newname が dic に存在する間、次を繰り返します。
      • dic[name] を +1 します。
      • newname := name + '(' + dic[name] + ')' を更新します。
    • dic[newname] := 1 を設定します。
    • res の末尾に newname を追加します。
• 最後に res を返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

from collections import defaultdict

def solve(names):
    dic = defaultdict(int)
    res = []
    for name in names:
        if name not in dic:
            dic[name] += 1
            res.append(name)
        else:
            newname = name + '(' + str(dic[name]) + ')'
            while newname in dic:
                dic[name] += 1
                newname = name + '(' + str(dic[name]) + ')'
            dic[newname] = 1
            res.append(newname)
    return res

names = ["my_dir","my_dir(1)","my_new_dir","my_new_dir","abc"]
print(solve(names))

入力

["my_dir","my_dir(1)","my_new_dir","my_new_dir","abc"]

出力

['my_dir', 'my_dir(1)', 'my_new_dir', 'my_new_dir(1)', 'abc']

アルゴリズムのポイント

このアルゴリズムでは、collections.defaultdict を活用して各名前の出現回数を効率的に管理しています。初めて登場する名前はそのまま使用し、既に存在する名前に対しては「(カウント数)」という接尾辞を付けた候補を生成します。その候補も既に存在する場合は、カウントを増やしながら一意な名前が見つかるまで探索を続けます。この仕組みにより、シンプルなコードでありながら、ファイルシステムにおける実際の命名規則と同じ動作を再現できるのが特徴です。