[paiza]プリーズ、プリーズ、交換しましょ（本の整理 (paizaランク A 相当)

# 赤・緑から剣・盾もやっとる（第1世代～
Poke Goに関しては、
オー◯ド「そこに３人の社畜がおるじゃろ？」
1. 上司や会社の命令にしたがいます。イエスマン
1. 残業はお客様へのサービスです。サビザン
1. 仕事が趣味です。ワカホリ

https://paiza.jp/works/mondai/real_event/book_sort


# チェック処理とかは端折ってる
/** ここから定型文 */
ここで記載したクラスについては、
[こっちの記事](https://qiita.com/AsilHatake/items/40204293bdf59cb9f9d8)に書いてある、標準入力をList化したりしてるMainクラスから呼び出す予定だし・なんか継承したりしてるYO!!

ちな、Mainを実行して標準入力から入力するのクソ面倒くさいので、
Java編については問題の入力例をパラメータにしたテストクラスとかも作って公開するYO!!

<details open><summary>開発・実行環境はこんな感じ</summary>

- VSCode
- Java 17
- jUnit 5.9
- maven

pom.xmlはこんな感じ

```xml:pom.xml
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>jp.co.asil</groupId>
    <artifactId>paiza202408</artifactId>
    <version>1.0-SNAPSHOT</version>

    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-engine</artifactId>
            <version>5.9.1</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
</project>
```

</details>
/** ここまで定型文 */

## 実装クラス（配列入れ替え版）
```java:BookSort.java
package jp.co.asil.paiza202408;

import java.util.List;

public class BookSort extends Question {

  public BookSort(List<String> list) {
    super(list);
  }

  /**
   * あなたはパイザ図書館で働く図書館員です。
   * 
   * パイザ図書館には N 冊の蔵書があります。この蔵書はすべて 1 段からなる本棚で管理されています。そして、それぞれの本には 1 から N
   * までの相異なる整数の ID がついています。本棚の本は ID 順に並んでいます。
   * 
   * しかし、ある日、あなたが蔵書の点検をしていると、本棚の本がバラバラに並べられていることに気づきました。
   * そこで、あなたは、次のルールに従って本を並び替えることにしました。
   * 
   * 次の手順を N 回繰り返す。
   * 
   * 1. i (1 ≦ i ≦ N) 回目の手順では、まず本棚の左から i 番目の位置に立つ。
   * 2. 左から i 番目の位置にある本から、本棚の右端にある本までのうち、最も ID が小さい本の位置を歩きながら見つける。この位置を j とする。
   * 3. i = j なら、何もしない。 i ≠ j なら、i 番目の本と j 番目の本を入れ替える。
   * 
   * 
   * 本を取り出して入れ替えるのには時間がかかります。そこで、このルールに従って本を整理するときに、何回本を入れ替える必要があるのかを計算してください。
   * 
   * 例)
   * 
   * 5 冊の本が、本棚に次の順番で並んでいたとします。ただし、数字はそれぞれの本の ID を表します。
   * 
   * 5 4 3 2 1
   * 
   * このとき、ルールに従うと、次のように本が整理されます。
   * 
   * i = 1 のとき (1 番目の本と 5 番目の本の位置が入れ替わる)
   * 
   * 1 4 3 2 5
   * 
   * i = 2 のとき (2 番目の本と 4 番目の本の位置が入れ替わる)
   * 
   * 1 2 3 4 5
   * 
   * i = 3 のとき
   * 
   * 1 2 3 4 5
   * 
   * i = 4 のとき
   * 
   * 1 2 3 4 5
   * 
   * i = 5 のとき
   * 
   * 1 2 3 4 5
   * 
   * 本の交換は i = 1 のときと i = 2 のときのみ起こっているので、このときの出力は 2 となります。
   */
  @Override
  public List<String> answer() {
    int[] sortTarget = List.of(list.get(1).split(" ")).stream().mapToInt(Integer::parseInt).toArray();
    int swapCnt = 0;
    for (int i = 0; i < sortTarget.length; i++) {
      int minIndex = i;
      for (int j = i + 1; j < sortTarget.length; j++) {
        if (sortTarget[j] < sortTarget[minIndex]) {
          minIndex = j;
        }
      }
      if (minIndex != i) {
        int temp = sortTarget[i];
        sortTarget[i] = sortTarget[minIndex];
        sortTarget[minIndex] = temp;
        swapCnt++;
      }
    }
    return List.of(String.valueOf(swapCnt));
  }
}
```

## 実装クラス（List入れ替え版）
```java:BookSort.java
package jp.co.asil.paiza202408;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BookSort extends Question {

  public BookSort(List<String> list) {
    super(list);
  }

  /**
   * あなたはパイザ図書館で働く図書館員です。
   * 
   * パイザ図書館には N 冊の蔵書があります。この蔵書はすべて 1 段からなる本棚で管理されています。そして、それぞれの本には 1 から N
   * までの相異なる整数の ID がついています。本棚の本は ID 順に並んでいます。
   * 
   * しかし、ある日、あなたが蔵書の点検をしていると、本棚の本がバラバラに並べられていることに気づきました。
   * そこで、あなたは、次のルールに従って本を並び替えることにしました。
   * 
   * 次の手順を N 回繰り返す。
   * 
   * 1. i (1 ≦ i ≦ N) 回目の手順では、まず本棚の左から i 番目の位置に立つ。
   * 2. 左から i 番目の位置にある本から、本棚の右端にある本までのうち、最も ID が小さい本の位置を歩きながら見つける。この位置を j とする。
   * 3. i = j なら、何もしない。 i ≠ j なら、i 番目の本と j 番目の本を入れ替える。
   * 
   * 
   * 本を取り出して入れ替えるのには時間がかかります。そこで、このルールに従って本を整理するときに、何回本を入れ替える必要があるのかを計算してください。
   * 
   * 例)
   * 
   * 5 冊の本が、本棚に次の順番で並んでいたとします。ただし、数字はそれぞれの本の ID を表します。
   * 
   * 5 4 3 2 1
   * 
   * このとき、ルールに従うと、次のように本が整理されます。
   * 
   * i = 1 のとき (1 番目の本と 5 番目の本の位置が入れ替わる)
   * 
   * 1 4 3 2 5
   * 
   * i = 2 のとき (2 番目の本と 4 番目の本の位置が入れ替わる)
   * 
   * 1 2 3 4 5
   * 
   * i = 3 のとき
   * 
   * 1 2 3 4 5
   * 
   * i = 4 のとき
   * 
   * 1 2 3 4 5
   * 
   * i = 5 のとき
   * 
   * 1 2 3 4 5
   * 
   * 本の交換は i = 1 のときと i = 2 のときのみ起こっているので、このときの出力は 2 となります。
   */
  @Override
  public List<String> answer() {
    List<Integer> sortTarget = new ArrayList<>(
        List.of(list.get(1).split(" ")).stream().mapToInt(Integer::parseInt).boxed().toList());
    int swapCnt = 0;
    for (int i = 0; i < sortTarget.size(); i++) {
      int minIndex = i;
      for (int j = i + 1; j < sortTarget.size(); j++)
        if (sortTarget.get(j) < sortTarget.get(minIndex))
          minIndex = j;

      if (minIndex != i) {
        Collections.swap(sortTarget, i, minIndex);
        swapCnt++;
      }
    }
    return List.of(String.valueOf(swapCnt));
  }
}

```

## 実装クラス 
```java:BookSortTest.java
package jp.co.asil.paiza202408;

import static org.junit.jupiter.api.Assertions.assertEquals;

import java.util.List;

import org.junit.jupiter.api.Test;

public class BookSortTest {
  @Test
  void testAnswer1() {
    BookSort testClass = new BookSort(List.of("5",
        "5 4 3 2 1"));
    assertEquals(testClass.answer().get(0), "2");
  }

  @Test
  void testAnswer2() {
    BookSort testClass = new BookSort(List.of("10",
        "8 7 9 1 5 6 2 10 4 3"));
    assertEquals(testClass.answer().get(0), "6");
  }
}
```

# 配列でもListでもどっちでもええんやで？
よくある形として配列のインデックス番号をチクチク入れ替えるっていう手法がよくあるかと思いますが、
JavaのCollectionsクラスにはswapという便利なメソッドが有るので、ソレを使った版も載せて見ました。

# Listを使う方の注意点
`Collections.swap`を使うときの注意点として、
swapする対象のListが**mutable(可変)**なものじゃないと、
`UnsupportedOperationException `が発生してしまうということ。

List.ofとかで作られたListは**immutable(不変)**なリストなので、
ArrayListなんかでラップしてあげてから使うとよろし。