【Python3】本の整理 (paizaランク A 相当)をやってみた

このコードでは、本の位置情報を記録する配列を用いて、効率的に交換回数を計算しています。

# 入力を読み込む
N = int(input())
shelf = [int(x) - 1 for x in input().split()]

# 各本の位置を記録する配列を用意
pos = [-1] * N
for i in range(N):
    pos[shelf[i]] = i

# 交換回数を記録する変数
ans = 0

# 本棚の本を並び替える処理
for i in range(N):
    # 既に正しい位置にある本はスキップ
    if shelf[i] == i:
        continue
    
    # 交換回数を増やす
    ans += 1
    
    # i番目の本と現在の正しい位置にある本を交換
    shelf[pos[i]] = shelf[i]
    pos[shelf[i]] = pos[i]

# 交換回数を出力
print(ans)

プログラムの説明

1. 入力の読み込み:

   • 最初の行で本の冊数 N を取得します。
   • 次の行で本棚の本のIDを取得し、0ベースのインデックスに変換して shelf リストに格納します。

2. 位置情報の記録:

   • pos 配列を作成し、各本のIDの現在の位置を記録します。

3. 交換回数の計算:

   • 本棚を左から順に確認し、正しい位置にない本を見つけた場合、交換を行います。
   • 交換回数を ans にカウントします。
   • 交換後、shelf と pos の情報を更新します。

4. 結果の出力:

   • 最終的な交換回数 ans を出力します。

このプログラムは効率的に本の交換回数を計算し、必要な計算量を最小限に抑えています。