[Ruby]paiza Cランクレベルアップメニュー ソート (paizaランク C 相当)の解説

こんにちは！じゃいごテックのあつしです。

今回はpaiza Cランクレベルアップメニュー からソートという問題を解説します。

この問題集は並び替えに関する3個のSTEP問題(D級)とFINAL問題(C級)で構成されていて、STEP問題を解いて行けばFINAL問題も解けるはず！となっています。

STEP問題を解いてみる

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

STEP1: 昇順ソート (paizaランク D 相当)

STEP1 はn個の改行区切りの整数を昇順(小さい数からの順)に並び替えて改行区切りで出力する問題です。

解答例

<<EOS

入力例1
2
4
3

出力例1
3
4

入力例2
3
2
3
1

出力例2
1
2
3

EOS

# [解答例1]
n = gets.to_i
ary = []
n.times do
  t_n = gets.to_i
  inserted = false
  ary.each_with_index do |a_n, idx|
    if t_n < a_n
      ary.insert(idx, t_n)
      inserted = true
      break
    end
  end
  ary << t_n if not inserted
end
puts ary

# [解答例2]
n = gets.to_i
ary = n.times.map { gets.to_i }.sort
puts ary

解答例1は、整数t_nを受け取り配列aryの先頭から順に値とインデックスを参照し、整数t_nより参照した整数a_nが大きければ、現在のインデックスidxへ整数t_nを挿入します。
最後まで挿入しなかった場合(inserted=false)は整数t_nが一番大きいということなので、配列aryの末尾に整数t_nを挿入します。

解答例2は、n個の改行区切りの整数を一旦全部受け取って配列にしたものをsortメソッドで昇順に並び替えて配列aryに格納しています。

STEP2: 降順ソート (paizaランク D 相当)

STEP2 はn個の改行区切りの整数を降順(大きい数からの順)に並び替えて改行区切りで出力する問題です。

解答例

<<EOS
 
入力例1
2
4
3

出力例1
4
3

入力例2
3
2
3
1

出力例2
3
2
1

EOS

# [解答例1]
n = gets.to_i
ary = []
n.times do
  t_n = gets.to_i
  inserted = false
  ary.each_with_index do |a_n, idx|
    if t_n > a_n
      ary.insert(idx, t_n)
      inserted = true
      break
    end
  end
  ary << t_n if not inserted
end
puts ary

# [解答例2]
n = gets.to_i
ary = n.times.map { gets.to_i }.sort.reverse
puts ary

解答例1は、整数t_nを受け取り配列aryの先頭から順に値とインデックスを参照し、整数t_nより参照した整数a_nが小さければ、現在のインデックスidxへ整数t_nを挿入します。
最後まで挿入しなかった場合(inserted=false)は整数t_nが一番小さいということなので、配列aryの末尾に整数t_nを挿入します。

解答例2は、n個の改行区切りの整数を一旦全部受け取って配列にしたものをsortメソッド.reverseメソッドで昇順の逆（つまり降順）に並び替えて、配列aryに格納しています。

STEP3: 辞書式ソート (paizaランク D 相当)

STEP3 はn組の整数a, bが与えられ、整数aの降順で整数aが同じ場合、整数bの降順（多重キー）で並び替える問題です。

<<EOS

入力例1
2
1 3
2 2

出力例1
2 2
1 3

入力例2
3
2 2
2 3
3 1

出力例2
3 1
2 3
2 2

EOS

# [解答例1]
n = gets.to_i
ary = []
n.times do
  t_a, t_b = gets.split.map(&:to_i)
  inserted = false
  ary.each_with_index do |items, idx|
    a_a, a_b = items
    if a_a < t_a || a_a == t_a && a_b < t_b
      ary.insert(idx, [t_a, t_b])
      inserted = true
      break
    end
  end
  ary << [t_a, t_b] if not inserted
end
ary.each { |item| puts item.join(" ") }

# [解答例2]
n = gets.to_i
ary = n.times.map { gets.split.map(&:to_i) }
ary.sort_by { |x| [x[0], x[1]] }.reverse.each do |item|
  puts item.join(" ")
end

解答例1は、整数a, bを受け取り配列aryの先頭から順に値とインデックスを参照し、「整数t_aより、参照した整数a_aが小さい」、または「整数t_aと整数a_aが等しく、かつ整数t_bより整数a_bが小さい」場合、現在のインデックスidxへ配列[t_a, t_b]を挿入します。
最後まで挿入しなかった場合(inserted=false)は整数t_aも整数t_bも一番小さいということなので、配列aryの末尾に配列[t_a, t_b]を挿入します。
ループを抜けたら二次元配列aryの行を改行区切り、行の中の各要素を半角スペース区切りに整えて出力します。

解答例2は、n個の改行区切りの整数を一旦全部受け取って配列にしたものをsort_byメソッド.reverseメソッドで整数aの昇順で整数bの昇順の逆（つまり降順）に並び替えて、出力しています。

ソート (paizaランク C 相当) を解いてみる

※ paiza Cランクレベルアップメニューより

問題

N
g_1 s_1
...
g_N s_N

攻略ポイント

問題を解く流れ

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

INPUT1 = <<~"EOS"
  2
  2 1
  1 2
EOS
OUTPUT1 = <<~"EOS"
  1 2
  2 1
EOS

INPUT2 = <<~"EOS"
  4
  2 3
  0 4
  5 0
  3 3
EOS
OUTPUT2 = <<~"EOS"
  0 4
  3 3
  2 3
  5 0
EOS

# 確認用コード
p INPUT1
# > "2\n2 1\n1 2\n"
p INPUT2
# > "4\n2 3\n0 4\n5 0\n3 3\n"

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

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

入力された文字列を改行で分割し、1行目で整数nを取得、続くn行で半角スペース区切りの整数のペア配列を配列ary に代入します。（二次元配列になります）

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n = input_lines.shift.to_i
  ary = input_lines.shift(n).map do |line|
    line.split.map(&:to_i)
  end

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

# 確認用コード
p solve(INPUT1)
# > [2, [[2, 1], [1, 2]]]
p solve(INPUT2)
# > [4, [[2, 3], [0, 4], [5, 0], [3, 3]]]

整数nと配列aryのデータが正しく受け取れていれば、solve メソッドに並び替えの処理を追加していきます。

• ソート済みの配列sorted_aryを空配列で初期化ます。
• 配列aryを先頭から参照するループの中に、配列sorted_aryを先頭からインデックスと共に参照するループを設定します。
• 配列aryの金t_g・銀t_sと配列sorted_aryの金a_g・銀a_sを比較します。
  • t_sがa_sより大きい場合、又はt_sとa_sが等しくかつt_sがa_sより大きい場合、参照中のsorted_aryのインデックス番号に配列[t_g, t_s]を挿入します。
  • 配列sorted_aryの最後まで挿入条件を満たさなかった場合(inserted=false)、配列sorted_aryの末尾に配列[t_g,t_s]を追加します。

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n = input_lines.shift.to_i
  ary = input_lines.shift(n).map do |line|
    line.split.map(&:to_i)
  end

  # 銀の降順で金の降順に並び替える
  sorted_ary = []
  ary.each do |t_g, t_s|
    inserted = false
    sorted_ary.each_with_index do |item, idx|
      a_g, a_s = item
      if t_s > a_s || t_s == a_s && t_g > a_g
        sorted_ary.insert(idx, [t_g, t_s])
        inserted = true
        break
      end
    end
    sorted_ary << [t_g, t_s] if not inserted
  end

  # 確認用コード
  sorted_ary
end

# 確認用コード
p solve(INPUT1)
# > [[1, 2], [2, 1]]
p solve(INPUT1) == OUTPUT1
# > false
p solve(INPUT2)
# > [[0, 4], [3, 3], [2, 3], [5, 0]]
p solve(INPUT2) == OUTPUT2
# > false

正しく並び替えが出来ていれば、あとは出力形式を整えれば完成です。

p solve(INPUT1) を puts solve(STDIN.read) に変更すれば正解となりますが、p solve(INPUT1) == OUTPUT1 -> true を確認するために、結果を改行区切りの文字列に変換して、末尾にも改行を加えます。

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n = input_lines.shift.to_i
  ary = input_lines.shift(n).map do |line|
    line.split.map(&:to_i)
  end

  # 銀の降順で金の降順に並び替える
  sorted_ary = []
  ary.each do |t_g, t_s|
    inserted = false
    sorted_ary.each_with_index do |item, idx|
      a_g, a_s = item
      if t_s > a_s || t_s == a_s && t_g > a_g
        sorted_ary.insert(idx, [t_g, t_s])
        inserted = true
        break
      end
    end
    sorted_ary << [t_g, t_s] if not inserted
  end

  # 行を改行で連結、行の要素を半角スペースで連結にして末尾に改行を追加
  sorted_ary.map { |item| item.join(" ") }.join("\n") << "\n"
end

# 確認用コード
p solve(INPUT1)
# > "1 2\n2 1\n"
p solve(INPUT1) == OUTPUT1
# > true
p solve(INPUT2)
# > "0 4\n3 3\n2 3\n5 0\n"
p solve(INPUT2) == OUTPUT2
# > true

確認用コードを標準入力からのデータ受け取りに変更して、動作確認をしたら提出します。
複数行のデータ受け取りなので STDIN.read を使います。（入力終了は Ctrl+D 又は Ctrl+Z)

解答コード

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n = input_lines.shift.to_i
  ary = input_lines.shift(n).map do |line|
    line.split.map(&:to_i)
  end

  # 銀の降順で金の降順に並び替える
  sorted_ary = []
  ary.each do |t_g, t_s|
    inserted = false
    sorted_ary.each_with_index do |item, idx|
      a_g, a_s = item
      if t_s > a_s || t_s == a_s && t_g > a_g
        sorted_ary.insert(idx, [t_g, t_s])
        inserted = true
        break
      end
    end
    sorted_ary << [t_g, t_s] if not inserted
  end

  # 行を改行で連結、行の要素を半角スペースで連結にして末尾に改行を追加
  sorted_ary.map { |item| item.join(" ") }.join("\n") << "\n"
end

# 提出用コード
puts solve(STDIN.read)

他の解答例

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n = input_lines.shift.to_i
  ary = input_lines.shift(n).map { |line| line.split.map(&:to_i) }
  
  # 銀の降順で金の降順に並び替える
  ary.sort_by! { |x| [x[1], x[0]] }.reverse!

  # 行を改行で連結、行の要素を半角スペースで連結にして末尾に改行を追加
  ary.map { |item| item.join(" ") }.join("\n") << "\n"
end

puts solve(STDIN.read)

計算量のお話

今回は勉強なので自前で挿入ソートを実装してみましたが、計算量がO(n²)でかなり遅いです。Rubyのsortメソッドはクイックソートを使っているらしいのでO(n log n)となります。なので普段はsortメソッドを使っておきましょう。

どの位違うのか計測してみたところ、下記の結果になりました。
今回の問題ではデータ数が最大50件なので合格となりますが、データ数が10,000件だとタイムオーバーになるということですね。

def solve1(input_lines)
  sorted_ary = []
  input_lines.each do |t_g, t_s|
    inserted = false
    sorted_ary.each_with_index do |items, idx|
      a_g, a_s = items
      if t_s > a_s || t_s == a_s && t_g > a_g
        ary.insert(idx, [t_g, t_s])
        inserted = true
        break
      end
    end
    sorted_ary << [t_g, t_s] if not inserted
  end
  sorted_ary.map { |item| item.join(" ") }.join("\n") << "\n"
end

def solve2(input_lines)
  ary = input_lines
  ary.sort_by! { |x| [x[1], x[0]] }.reverse!
  ary.map { |item| item.join(" ") }.join("\n") << "\n"
end

srand(0)
n = 10 ** 4
max_num = 1000
ary = Array.new(n) { [rand(max_num), rand(max_num)] }

start_time = Time.now
solve1(ary)
puts Time.now - start_time

今回のまとめ

この問題集を通して以下の操作を覚えることが出来ました。

• 複数行のデータの受け取り
• 文字列の分割、結合
• 文字列型⇔整数型の変換
• 多次元配列
• 多重ループ
• 条件分岐
• 多重キーでのソート

多重ループを扱うようになったら、正しい回答に加えてタイムオーバーについても気を付ける必要があります。

テストケースの条件を確認して、最大の計算量をざっくり掴んでおくと良いと思います！