【Python】フォルダ移動ログからホームディレクトリへ戻るための最小操作回数を求めるプログラム

問題の概要

フォルダへの移動履歴(ログ)が与えられ、その中には次のような記号が含まれているものとします。

• "../" : 現在のフォルダから親フォルダへ移動する(すでにメインフォルダにいる場合は位置を変えない)。
• "./" : 現在のフォルダにとどまる。
• "x/" : x という名前の子フォルダへ移動する。

このログをもとに、最後に到達したフォルダからメインフォルダ(ホーム)へ戻るために必要な最小の操作回数を求めるのが目的です。

たとえば、入力が logs = ["Dir1/","Dir2/","../","Dir2/","Dir3/","./"] の場合、出力は 3 になります。

図を見るとわかるように、ホームに戻るまでに3回ステップバックする必要があります。

解き方(アルゴリズム)

この問題はスタックを使うことでシンプルかつ効率的に解けます。手順は以下のとおりです。

• 空のスタック stk を用意する。
• logs 内の各要素 i について、次の処理を繰り返す。
  • i が "../" であり、かつ stk のサイズが 0 より大きい場合は、stk の末尾の要素を削除する(pop)。
  • i が "./" でも "../" でもない場合は、i を stk の末尾に追加する(push)。
  • それ以外の場合は、何もせず次の反復へ進む。
• 最後に、stk に残っている要素数を返す。

スタックに残った要素数が、そのままホームへ戻るために必要な "../" の操作回数に対応します。メインフォルダより上には戻れないため、stk が空のときの "../" は無視される点がポイントです。

Pythonでの実装例

以下の実装を見ると、動作がより理解しやすくなります。

def solve(logs):
    stk = []
    for i in logs:
        if i == "../" and len(stk) > 0:
            stk.pop()
        elif i != "./" and i != "../":
            stk.append(i)
        else:
            continue
    return len(stk)

logs = ["Dir1/","Dir2/","../","Dir2/","Dir3/","./"]
print(solve(logs))

入力

["Dir1/","Dir2/","../","Dir2/","Dir3/","./"]

出力

3

計算量について

時間計算量: O(n) ― ログの各エントリを一度だけ処理すればよいため、ログの長さに比例して処理が完了します。
空間計算量: O(n) ― 最悪ケースでは、すべてのフォルダ移動がスタックに積まれる可能性があります。