今回はpaiza 線形探索メニュー セクション2【最大最小】を解説します。
セクション2【最大最小】は、与えられた数列データの中から、最大値・最小値を探し出す問題です。
2個のSTEP問題(D級)とFINAL問題(C級)で構成されていて、STEP問題を解いて行けばFINAL問題も解けるはず！となっています。
- STEP1：要素数2個の数列aの最大値と最小値を出力する
- STEP2：要素数10個の数列aの最大値と最小値を出力する
- FINAL：要素数n個の数列aの最大値と最小値を出力する
STEP問題を解いてみる
簡単な解説は付けていますが、難しいと感じたら下記の記事も参考にしてみて下さい。
STEP1: 2変数の最大最小 (paizaランク D 相当)
要素数2個の数列aの最大値と最小値をスペースで連結して出力する問題です。
解答例1
INPUT1 = <<~"EOS"
-11 10
EOS
OUTPUT1 = <<~"EOS"
10 -11
EOS
def solve1(input_lines)
ary = input_lines.split.map(&:to_i)
if ary[0] < ary[1]
ary[0], ary[1] = ary[1], ary[0]
end
ary.join(" ")
end
puts solve1(STDIN.read)
# puts solve1(INPUT1)
# 10 -11
2つの要素ary[0]とary[1]を比較して、先頭に最大値が来るように並び替えてから数列aryの要素を半角スペースで連結して出力します。
解答例2
INPUT1 = <<~"EOS"
-11 10
EOS
OUTPUT1 = <<~"EOS"
10 -11
EOS
def solve2(input_lines)
ary = input_lines.split.map(&:to_i)
ary.minmax.reverse.join(" ")
end
puts solve2(STDIN.read)
# puts solve2(INPUT1)
# 10 -11
minmaxメソッドで数列aryの最小値・最大値の配列を生成し、先頭に最大値が来るように並び替えてから、aryの要素を半角スペースで連結して出力します。
STEP2: 10変数の最大最小 (paizaランク D 相当)
要素数10個の数列aの最大値と最小値をスペースで連結して出力する問題です。
解答例1
INPUT1 = <<~"EOS"
-11 10 0 9 6 -10 5 3 2 -8
EOS
OUTPUT1 = <<~"EOS"
10 -11
EOS
def solve1(input_lines)
ary = input_lines.split.map(&:to_i)
max_val = -Float::INFINITY
min_val = Float::INFINITY
ary.each do |val|
max_val = val if max_val < val
min_val = val if min_val > val
end
[max_val, min_val].join(" ")
end
max_val=-Float::INFINITY(-無限大), min_val=Float::INFINITY(+無限大)で変数を初期化する数列aryの先頭から順に値を参照する- max_valより大きかったらmax_valを更新する
- min_valより小さかったらmin_valを更新する
max_val, min_valを半角スペースで連結する
解答例2
INPUT1 = <<~"EOS"
-11 10 0 9 6 -10 5 3 2 -8
EOS
OUTPUT1 = <<~"EOS"
10 -11
EOS
def solve2(input_lines)
ary = input_lines.split.map(&:to_i)
ary.minmax.reverse.join(" ")
end
puts solve2(STDIN.read)
# puts solve2(INPUT1)
# 10 -11
minmaxメソッドで数列aryの最小値・最大値の配列を生成し、先頭に最大値が来るように並び替えてから、aryの要素を半角スペースで連結して出力します。（STEP1の解答例2と同じ）
n 変数の最大最小 (paizaランク C 相当)を解いてみる
※ paiza 線形探索メニューより
問題
整数 n と、数列 a_1, ... , a_n が与えられます。
数列の最大値と最小値をこの順に半角スペース区切りで出力してください。
入力される値
入力は以下のフォーマットで与えられます。
n a_1 a_2 ... a_n
- 1行目に数列の長さを表す整数 n が与えられます。
- 2行目に、数列の値 a_i が先頭から順に半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
期待する出力
数列の最大値と最小値をこの順に半角スペース区切りで出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
条件
すべてのテストケースにおいて、以下の条件をみたします。
- 入力は全て整数
- 1 ≦ n ≦ 10,000
- -1,000,000,000 ≦ a_i ≦ 1,000,000,000
- 入力例1
- 5
10 -19 14 8 -90
- 出力例1
- 14 -90
攻略ポイント
ポイント
- 数列を先頭から順番に参照して最大値・最小値を更新するかを判定する
デバッグを楽にするためにメソッドを作成します。メソッドについては下記の記事も参考にしてみて下さい。
問題を解く流れ
入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。
INPUT1 = <<~"EOS" 5 10 -19 14 8 -90 EOS OUTPUT1 = <<~"EOS" 14 -90 EOS # 確認用コード p INPUT1 # > "5\n10 -19 14 8 -90\n" p OUTPUT1 # > "14 -90\n"
続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。
まず、入力データを受け取る処理を書きます。
def solve(input_lines) # 入力受け取り n, *ary = input_lines.split.map(&:to_i) # 確認用コード [n, ary] end # 確認用コード p solve(INPUT1) # > [5, [10, -19, 14, 8, -90]]
データが正しく受け取れていれば、solve メソッドに最大値・最小値を探す処理を追加していきます。
max_val=-Float::INFINITY(-無限大), min_val=Float::INFINITY(+無限大)で変数を初期化する数列aryの先頭から順に値を参照する- max_valより大きかったらmax_valを更新する
- min_valより小さかったらmin_valを更新する
def solve(input_lines)
# 入力受け取り
n, *ary = input_lines.split.map(&:to_i)
max_val = -Float::INFINITY
min_val = Float::INFINITY
ary.each do |val|
max_val = val if val > max_val
min_val = val if val < min_val
end
# 確認用コード
[max_val, min_val]
end
# 確認用コード
p solve(INPUT1)
# > [14, -90]
p solve(INPUT1) == OUTPUT1
# > false
あとは出力形式を整えれば完成です。
p solve(INPUT1) == OUTPUT1 -> true を確認するために、最大値と最小値を半角スペースで連結した文字列に変換して末尾に改行を加えます。
def solve(input_lines)
# 入力受け取り
n, *ary = input_lines.split.map(&:to_i)
max_val = -Float::INFINITY
min_val = Float::INFINITY
ary.each do |val|
max_val = val if val > max_val
min_val = val if val < min_val
end
# 最大値・最小値を半角スペースで連結して末尾に改行を追加
[max_val, min_val].join(" ") << "\n"
end
# 確認用コード
p solve(INPUT1)
# > [14, -90]
p solve(INPUT1) == OUTPUT1
# > false
確認用コードを標準入力からのデータ受け取りに変更、標準出力をpメソッドからputsメソッドに変更して、動作確認をしたら提出します。
複数行のデータ受け取りなので STDIN.read を使います。（入力終了は Ctrl+D 又は Ctrl+Z)
解答コード
def solve(input_lines)
# 入力受け取り
n, *ary = input_lines.split.map(&:to_i)
max_val = -Float::INFINITY
min_val = Float::INFINITY
ary.each do |val|
max_val = val if val > max_val
min_val = val if val < min_val
end
# 最大値・最小値を半角スペースで連結して末尾に改行を追加
[max_val, min_val].join(" ") << "\n"
end
puts solve(STDIN.read)
他の解答例
STEP問題と同様、minmaxメソッドを使うと簡単です。
def solve(input_lines)
n, *ary = input_lines.split.map(&:to_i)
ary.minmax.reverse.join(" ")
end
今回のまとめ
セクション2では、数列の中から最大値・最小値を探し出す方法を実装しました。
練習としてループで最大値・最小値を探索しましたが、max, min, maxminメソッドを使うと簡単に書けますね！
