0. どんな問題？（問題の概要）
1〜N のランダムな数値が円環状に並んでいます。
「1から順に小さい要素を外に出していく」とき、全要素が出終わるまでに円環を何周する必要があるかを求める問題です。
※特定の問題を抽象化して、「配列表列のシミュレーション」として整理しています。
1. つまずいたポイント
最初は問題の指示通りに「1台（1要素）ずつ愚直に動かして探す」というシミュレーションを書きました。
mycode.py
N = int(input())
cars = [int(input()) for _ in range(N)]
#入力を素直に一行ずつ配列に代入していく
track_count = [0 for _ in range(N)]
#車の数と同じ大きさの０が入った配列を作り、周回数を書き込んでいく
MIN = min(cars)
#要素の中での最小値を出して、出て行ったものは数えなくてもよくなるよう、増やしていく
while MIN <= N:
for i in range(N):
#律儀に一台ずつ数えていく
if (MIN != cars[i]):
track_count[i] += 1
else:
MIN += 1
for k in range(N):
if N == cars[k]:
print(track_count[k])
else:
pass
#最終的に最後に出て行ったものの周回数を出力したかった
2. 発想の転換：「車番→位置」の逆引き配列
「1から順番に出す」なら、「1はどこ？」「2はどこ？」が即座に分かればいいはずです。
そこで、配列のインデックスと値をひっくり返した pos[値] = 初期位置 という「逆引き配列」を作ります。
これなら、「次に欲しい値が何番目にあるか」を $O(1)$（一瞬） で検索できるようになります。
周回が必要になる条件は非常にシンプルで、「値 $k$ の位置より、値 $k+1$ の位置の方が手前にあった場合（＝すでに出口を通り過ぎている場合）」 だけです。
つまり、全シミュレーションを行わなくても、位置関係の比較だけで周回数が求まります。
frac1.py
pos = [0] * (N + 1)
# 値 N をそのまま pos[N] として指定できるよう、サイズ N+1 で作成
for index, car in enumerate(cars):
# enumerate を使って「初期位置 (index)」と「値 (car)」を同時に取り出す
pos[car] = index
# pos[値] = 初期位置
3. 解答コード（素直な for ループ版）
まずは思考の流れをそのままコードにした、理解しやすい $O(N)$ 解法です。
for_ver.py
# STEP 1: 位置を記録する（逆引き配列の作成）
pos = [0] * (N + 1)
for i in range(N):
car = cars[i]
pos[car] = i # 値 car が何番目(i)にあるかを記録
# STEP 2: 隣り合う値の位置関係を比較する
laps = 0
for k in range(1, N):
# 値 k より 値 k+1 の方が手前にあったら、もう1周必要！
if pos[k] > pos[k + 1]:
laps += 1
print(laps)
4. さらにPythonらしく書くなら（zip と slice）
上記の for ループによる比較は、zip とスライスを使うことでインデックス変数（k や k+1）を書かずにスッキリ記述できます。
sophisticated_ver.py
import sys
def main():
# 標準入力から全データを一括取得（高速化）
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
cars = [int(x) for x in input_data[1:]]
# pos[v] : 値 v が初期位置の何番目(0-indexed)にいるかを記録
pos = [0] * (N + 1)
for index, car in enumerate(cars):
pos[car] = index
# slice と zip を使って pos[k] > pos[k+1] の回数を一気にカウント
# pos[1:N] -> 値 1 〜 N-1 の位置リスト
# pos[2:N+1] -> 値 2 〜 N の位置リスト
laps = sum(1 for p_current, p_next in zip(pos[1:N], pos[2:N+1]) if p_current > p_next)
print(laps)
if __name__ == "__main__":
main()
5. 学んだこと・まとめ
- 「特定の値がどこにあるか」を何度も参照するときは、pos[値] = インデックス の逆引き配列を作る
- シミュレーションで重くなりそうなときは、「実際に動かす」のではなく「位置関係の規則性」に落とし込めないかを考える
- 競技プログラミングやコードテストでは、愚直な $O(N^2)$ から $O(N)$ への転換がスコアを大きく分ける