[Ruby]paiza 線形探索メニュー 第k要素の探索

今回はpaiza 線形探索メニュー  セクション4【第k要素の探索】を解説します。

セクション4【第k要素の探索】は、与えられた数列データの中から、k番目に大きな値を探し出す問題です。

• STEP1：n個の数列aが与えられ、その中で2番目に大きな数を出力する
• FINAL：n個の数列aと整数kが与えられ、その中でk番目に大きな数を出力する

STEP問題を解いてみる

簡単な解説は付けていますが、難しいと感じたら下記の記事も参考にしてみて下さい。

STEP1: 2番目に大きな値 (paizaランク C 相当)

n個の数列aが与えられ、その中で2番目に大きな数を出力する問題です。

 解答例1

INPUT1 = <<~"EOS"
  5
  -9 10 6 0 -3
EOS
OUTPUT1 = <<~"EOS"
  6
EOS

def solve1(input_lines)
  n, *ary = input_lines.split.map(&:to_i)

  2.times do |i|
    0.upto(n - 2 - i) do |j|
      if ary[j] > ary[j + 1]
        ary[j], ary[j + 1] = ary[j + 1], ary[j]
      end
    end
  end

  ary[-2]
end

puts solve1(STDIN.read)
# puts solve1(INPUT1)
# > 6

• 整数n, 配列aryの入力データを受け取る
• i=0~1 (2回)の繰り返し処理を設定する
  ※ iの繰り返しをn-1回行えばバブルソートになりますね！
  • j=0~n-i-2 の繰り返し処理を設定する
    • もしary[j]がary[j+1]より大きかったら、ary[j]とary[j+1]を入れ替える

処理の流れ

i = 0, j = 0 ~ n - i - 2 (3) のループ開始

i = 0, j = 0 ~ n - i - 2 (3) のループ終了

i = 1, j = 0 ~ n - i - 2 (2) のループ開始

i = 1, j = 0 ~ n - i - 2 (2) のループ終了

解答例2

INPUT1 = <<~"EOS"
  5
  -9 10 6 0 -3
EOS
OUTPUT1 = <<~"EOS"
  6
EOS

def solve2(input_lines)
  n, *ary = input_lines.split.map(&:to_i)

  ary.sort[-2]
end

puts solve2(STDIN.read)
# > puts solve2(INPUT1)
# > 6

sortメソッドで、aryを昇順に並び替えて後ろから2番目の値を参照します。

解答例3

def solve3(input_lines)
  n, *ary = input_lines.split.map(&:to_i)

  ary.max(2).last
end

puts solve3(STDIN.read)
# puts solve3(INPUT1)
# > 6

maxメソッドで、引数にkを渡すとk番目までの大きい数を降順の配列で返します。

k番目に大きな値 (paizaランク C 相当)を解いてみる

※ paiza 線形探索メニューより

問題

攻略ポイント

問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<~"EOS"
  5
  -9 10 6 0 -3
  4
EOS
OUTPUT1 = <<~"EOS"
  -3
EOS

# 確認用コード
p INPUT1
# > "5\n-9 10 6 0 -3\n4\n"
p OUTPUT1
# > "-3\n"

続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。

まず、入力データを受け取る処理を書きます。

def solve(input_lines)
  n, *ary, k = input_lines.split.map(&:to_i)

  # 確認用コード
  [n, ary, k]
end

# 確認用コード
p solve(INPUT1)
# > [5, [-9, 10, 6, 0, -3], 4]

データが正しく受け取れていれば、solve メソッドに数列aryの中でk番目に大きな値を探索する処理を追加していきます。

• i=0~k-1 (k回)の繰り返し処理を設定する
  • j=0~n-i-2 の繰り返し処理を設定する
    • もしary[j]がary[j+1]より大きかったら、ary[j]とary[j+1]を入れ替える

def solve(input_lines)
  n, *ary, k = input_lines.split.map(&:to_i)

  k.times do |i|
    0.upto(n - 2 - i) do |j|
      if ary[j] > ary[j + 1]
        ary[j], ary[j + 1] = ary[j + 1], ary[j]
      end
    end
  end

  # 確認用コード
  ary
end

# 確認用コード
p solve(INPUT1)
# > [-9, -3, 0, 6, 10]
p solve(INPUT1) == OUTPUT1
# > false

あとはary[-k]（k番目に大きい数）を出力すれば完成です。

p solve(INPUT1) == OUTPUT1 -> true を確認するために、ary[-k]の値を文字列に変換して末尾に改行を加えます。

def solve(input_lines)
  n, *ary, k = input_lines.split.map(&:to_i)

  k.times do |i|
    0.upto(n - 2 - i) do |j|
      if ary[j] > ary[j + 1]
        ary[j], ary[j + 1] = ary[j + 1], ary[j]
      end
    end
  end

  # ary[-k] を文字列に変換して末尾に改行を追加
  ary[-k].to_s << "\n"
end

# 確認用コード
p solve(INPUT1)
# > "-3\n"
p solve(INPUT1) == OUTPUT1
# > true

確認用コードを標準入力からのデータ受け取りに変更、標準出力をpメソッドからputsメソッドに変更して、動作確認をしたら提出します。（STDIN.readの入力終了は Ctrl+D 又は Ctrl+Z)

解答コード

def solve(input_lines)
  n, *ary, k = input_lines.split.map(&:to_i)

  k.times do |i|
    0.upto(n - 2 - i) do |j|
      if ary[j] > ary[j + 1]
        ary[j], ary[j + 1] = ary[j + 1], ary[j]
      end
    end
  end

  # ary[-k] を文字列に変換して末尾に改行を追加
  ary[-k].to_s << "\n"
end

puts solve(STDIN.read)

他の解答例

STEP1と同様に以下の方法が使えます

• sortメソッドで配列aryを昇順に並び替えてからary[-k]を参照する
• maxメソッドの引数にkを与えて返ってきた配列の末尾を参照する

INPUT1 = <<~"EOS"
  5
  -9 10 6 0 -3
  4
EOS
OUTPUT1 = <<~"EOS"
  -3
EOS

def solve1(input_lines)
  n, *ary, k = input_lines.split.map(&:to_i)

  ary.sort[-k]
end

puts solve1(STDIN.read)
# puts solve1(INPUT1)
# > -3

def solve2(input_lines)
  n, *ary, k = input_lines.split.map(&:to_i)

  ary.max(k).last
end

puts solve2(STDIN.read)
# puts solve2(INPUT1)
# > -3

今回のまとめ

セクション4では、線形探索法（と言うかバブルソート）を使ってk番目に大きな要素の探索を行いました。
nの最大が10,000だったのでバブルソートO(n²)ではタイムオーバーになるかと思いましたが、何とか通過出来ました。
今回は勉強のために自前でアルゴリズムを実装しましたが、通常はsortメソッドかmax(k)メソッドを利用しましょう。

• バブルソートでテストケース12 (n=9805) にかかった時間 5.35秒
• sortメソッドでテストケース12 (n=9805) にかかった時間 0.12秒
• max(k)メソッドでテストケース12 (n=9805) にかかった時間 0.13秒

単純な処理なら組み込みメソッドを利用したほうが格段に速いですね！