今回はpaiza 線形探索メニュー セクション1【指定された値の探索】を解説します。
セクション1【指定された値の探索】は、与えられた数列データの中から、指定された値を探し出す問題です。
3個のSTEP問題(D級)とFINAL問題(D級)で構成されていて、STEP問題を解いて行けばFINAL問題も解けるはず！となっています。
- STEP1：要素数n個の数列aに整数kが何個あるか
- STEP2：要素数n個の数列aで整数kが最初に現れるのは数列の何番目か
- STEP3：要素数n個の数列aで整数kが最後に現れるのは数列の何番目か
- FINAL： 要素数n個の数列aで整数kが現れるのは数列の何番目か（全て）
STEP問題を解いてみる
簡単な解説は付けていますが、難しいと感じたら下記の記事も参考にしてみて下さい。
STEP1: 指定された値の個数 (paizaランク D 相当)
要素数n個の数列aに整数kが何個あるかを出力する問題です。
解答例1
INPUT1 = <<~"EOS"
5
-3 2 0 -1 2
2
EOS
OUTPUT1 = <<~"EOS"
2
EOS
def solve1(input_lines)
n, *ary, k = input_lines.split.map(&:to_i)
result = 0
ary.each do |num|
if num == k
result += 1
end
end
result
end
puts solve1(STDIN.read)
# puts solve1(INPUT1)
# > 2
eachメソッドで数列aryの先頭から順番に参照して、整数kがあれば探索結果resultをカウントアップします。
解答例2
INPUT1 = <<~"EOS" 5 -3 2 0 -1 2 2 EOS OUTPUT1 = <<~"EOS" 2 EOS def solve2(input_lines) n, *ary, k = input_lines.split.map(&:to_i) ary.count(k) end puts solve2(STDIN.read) # puts solve2(INPUT1) # > 2
countメソッドで数列aryに含まれる整数kの数をカウントします。
STEP2: 指定された値の位置 1 (paizaランク D 相当)
要素数n個の数列aで整数kが最初に現れるのは数列の何番目かを出力、見つからない場合は0を出力する問題です。
解答例1
INPUT1 = <<~"EOS"
5
-3 2 0 -1 2
2
EOS
OUTPUT1 = <<~"EOS"
2
EOS
def solve1(input_lines)
n, *ary, k = input_lines.split.map(&:to_i)
result = 0
1.upto(n) do |i|
if ary[i - 1] == k
result = i
break
end
end
result
end
puts solve1(STDIN.read)
# puts solve1(INPUT1)
# > 2
i = 1~nでループを設定して数列aryを先頭から順番に参照し、整数kがあればresult=iで更新してループを抜けます。
※ 数列aryのi番目の値はary[i-1]となります。
解答例2
INPUT1 = <<~"EOS" 5 -3 2 0 -1 2 2 EOS OUTPUT1 = <<~"EOS" 2 EOS def solve2(input_lines) n, *ary, k = input_lines.split.map(&:to_i) result = ary.index(k) result.nil? ? 0 : result + 1 end puts solve2(STDIN.read) # puts solve2(INPUT1) # > 2
indexメソッドで数列aryで整数kが最初に出現する添字（index）を求めます。
見つかった場合は添字、見つからなかった場合はnilが返ってくるので、条件分岐を使って0または添字+1を返します。
STEP3: 指定された値の位置 2 (paizaランク D 相当)
要素数n個の数列aで整数kが最後に現れるのは数列の何番目かを出力、見つからない場合は0を出力する問題です。
解答例1
INPUT1 = <<~"EOS"
5
-3 2 0 -1 2
2
EOS
OUTPUT1 = <<~"EOS"
5
EOS
def solve1(input_lines)
n, *ary, k = input_lines.split.map(&:to_i)
result = 0
n.downto(1) do |i|
if ary[i - 1] == k
result = i
break
end
end
result
end
puts solve1(STDIN.read)
# puts solve1(INPUT1)
# > 5
i = n~1でループを設定して数列aryを末尾から順番に参照し、整数kがあればresult=iで更新してループを抜けます。
※ 数列aryのi番目の値はary[i-1]となります。
解答例2
INPUT1 = <<~"EOS" 5 -3 2 0 -1 2 2 EOS OUTPUT1 = <<~"EOS" 5 EOS def solve2(input_lines) n, *ary, k = input_lines.split.map(&:to_i) result = ary.rindex(k) result.nil? ? 0 : result + 1 end puts solve2(STDIN.read) # puts solve2(INPUT1) # > 5
rindexメソッドで数列aryで整数kが最後に出現する添字（index）を求めます。
見つかった場合は添字、見つからなかった場合はnilが返ってくるので、条件分岐を使って0または添字+1を返します。
指定された値の位置 3 (paizaランク D 相当)を解いてみる
※ paiza 線形探索メニューより
問題
整数 n と、数列 a_1, ... , a_n と、整数 k が与えられます。
整数 k が数列の何番目にあるかを求めてください。最初の要素 (a_1) を 1 番目とします。
数列に整数 k が複数含まれている場合は、そのすべてについて何番目にあるかを求め、数列を先頭から見たときに現れる順にすべて出力してください。
ただし、整数 k が数列に含まれていない場合は、何も出力しないでください。
入力される値
入力は以下のフォーマットで与えられます。
n
a_1 a_2 ... a_n
k
- 1行目に、数列の長さを表す整数 n が与えられます。
- 2行目に、数列の値 a_i が半角スペース区切りで与えられます。
- 3行目に、整数 k が与えられます。
入力値最終行の末尾に改行が１つ入ります。
期待する出力
数列に含まれるすべての整数 k について、それぞれ何番目にあるかを、数列を先頭から見たときに現れる順に、改行区切りで出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
ただし、整数 k が数列に含まれていない場合は、何も出力しないでください。
条件
すべてのテストケースにおいて、以下の条件をみたします。
- 入力は全て整数
- 1 ≦ n ≦ 1,000
- -100 ≦ a_i ≦ 100
- -100 ≦ k ≦ 100
- 入力例1
- 5
-3 2 0 -1 2
2
- 出力例1
- 2
5
攻略ポイント
ポイント
- 数列を先頭から順番に参照して特定の値を一致するかを調べる
- 一致した場合、その要素の添え字を配列で記録する
デバッグを楽にするためにメソッドを作成します。メソッドについては下記の記事も参考にしてみて下さい。
問題を解く流れ
入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。
INPUT1 = <<~"EOS" 5 -3 2 0 -1 2 2 EOS OUTPUT1 = <<~"EOS" 2 5 EOS # 確認用コード p INPUT1 # > "5\n-3 2 0 -1 2\n2\n" p OUTPUT1 # > "2\n5\n"
続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。
まず、入力データを受け取る処理を書きます。
def solve(input_lines) # 入力受け取り n, *ary, k = input_lines.split.map(&:to_i) # 確認用コード [n, ary, k] end # 確認用コード p solve(INPUT1) # > [5, [-3, 2, 0, -1, 2], 2]
データが正しく受け取れていれば、solve メソッドに数列から指定された値を探す処理を追加していきます。
- 数列aryの先頭から順に参照して整数kと一致するかを調べる
- もし整数kと一致した場合、添え字を記録する
def solve(input_lines)
# 入力受け取り
n, *ary, k = input_lines.split.map(&:to_i)
result = []
1.upto(n) do |i|
if ary[i - 1] == k
result << i
end
end
# 確認用コード
result
end
# 確認用コード
p solve(INPUT1)
# > [2, 5]
p solve(INPUT1) == OUTPUT1
# > false
あとは出力形式を整えれば完成です。
p solve(INPUT1) == OUTPUT1 -> true を確認するために、結果の配列を改行区切りの文字列に変換して、末尾にも改行を加えます。
def solve(input_lines)
# 入力受け取り
n, *ary, k = input_lines.split.map(&:to_i)
result = []
1.upto(n) do |i|
if ary[i - 1] == k
result << i
end
end
# 探索結果を改行区切りにして末尾に改行を追加
result.join("\n") << "\n"
end
# 確認用コード
p solve(INPUT1)
# > "2\n5\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)
result = []
1.upto(n) do |i|
if ary[i - 1] == k
result << i
end
end
# 探索結果を改行区切りにして末尾に改行を追加
result.join("\n") << "\n"
end
puts solve(STDIN.read)
他の解答例
selectメソッドで条件に合致した全ての要素の配列を生成します。
def solve(input_lines)
n, *ary, k = input_lines.split.map(&:to_i)
1.upto(n).select { |i| ary[i - 1] == k }
end
puts solve(STDIN.read)
今回のまとめ
セクション１では、数列の中から特定の値の数・場所を探し出す方法を実装しました。
文字列の配列でも同じように特定の文字列を探し出すことができますね！
