[paiza]本の整理 (paizaランク A 相当)

なんだかんだでAランクまで来ちゃったよ。。。

最初にSランクの簡単そうなやつを1問解いてから、Dランクで無双がしたいという浅はかな理由で始めて、C・Bと特に面白いことも言えずにダラダラ解いて来たけど、とうとうAランク問題に突入しました。

面倒くさいので画面パタメータをListでもらった後のFunctionだけ

ちなみに引数のListを作ってる箇所はこっちの記事に書いてあるYO!!

bookSort.js

// [問題文（原文）]
// あなたはパイザ図書館で働く図書館員です。
// 
// パイザ図書館には 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 となります。
function bookSort(lines) {
  // 入力は以下のフォーマットで与えられます。
  // 
  // N
  // a_1 a_2 ... a_N
  // 
  // ・1 行目に本の冊数を表す整数 N が与えられます。
  // ・2 行目に、 1 番目の本の ID を表す整数 a_1、 2 番目の本の ID を表す整数 a_2、 ...、 N 番目の本の ID を表す整数 a_N がこの順に半角スペース区切りで与えられます。
  // ・入力は合計で 2 行となり、末尾に改行が 1 つ入ります。

  // 入力チェック面倒くさいので正常系のみ対応するよ
  let list = lines[1].split(" ").map(v => Number(v));
  let swapCnt = 0;
  for (let i = 0; i < list.length; i++) {
    let min = list[i];
    let minIdx = i;
    for (let j = i + 1; j < list.length; j++) {
      if (list[j] < min) {
        min = list[j];
        minIdx = j;
      }
    }
    if (minIdx !== i) {
      let tmp = list[i];
      list[i] = list[minIdx];
      list[minIdx] = tmp;
      swapCnt++;
    }
  }

  // 本の交換をする回数を整数で出力してください。
  console.log(swapCnt);
}

module.exports = {
  bookSort
};

ソートって結構色々種類あるけど、これは 選択ソートになるのかな？