解いてみた。「Aランク：本の整理」

問題

「Aランク：本の整理」

コード

Javaで解いてみました。

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int nN = sc.nextInt();
        int[] anBooks = new int[nN+1];

        // 本の並び順を格納
        for (int i = 1; i <= nN; i++) {
            anBooks[i] = sc.nextInt();
        }

        // 交換回数
        int nChange = 0;

        // 左からi冊目の本について
        for (int i = 1; i <= nN; i++) {
            // 番号がiなら、交換不要
            if (anBooks[i] == i) {
                continue;
            }

            // i+1番目以降にある、番号iの本を探し、交換する
            for (int j = i+1; j <= nN; j++) {
                if (anBooks[j] == i) {
                    int temp = anBooks[i];
                    anBooks[i] = anBooks[j];
                    anBooks[j] = temp;
                    nChange++;
                    break;
                }
            }
        }

        // 結果出力
        System.out.println(nChange);
    }
}

解説

標準入力からの数値の読み取り

Scanner インスタンスを作り、nextInt()メソッドで数値（本の冊数）を取得しています。

本の並び順を取得

標準入力から anBooks[] に本の並び順を格納しています。

初期設定

交換回数 nChange に0を設定します。

本の並び替え

左からi冊目の本について調べる。

本の番号がiである場合。

交換不要のため、次の本へ。

本の番号がi以外の場合。

i+1冊目以降の本を調べていき、番号iの本を見つけたら、その本とi冊目の本を交換し、交換回数を１増やす。

補足

ここでは、i番目とj番目（番号iの本があった場所）の交換を行なっていますが、速さを少しでも追求するならば、

    int temp = anBooks[i];
    anBooks[i] = anBooks[j];
    anBooks[j] = temp;

を

    anBooks[j] = anBooks[i];

にするとStep数を減らすことができます。（左からi冊目については、この問題では、もう使用しないので、anBooks[i]を更新する必要はない。）

結果出力

交換回数 nChange を表示します。