[Ruby]paiza スキルチェック過去問題セット 検索履歴 (paizaランク C 相当)の解説

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

今回はpaizaレベルアップ問題集から検索履歴という問題を解説していきたいと思います。こちらは過去にスキルチェックで実際に出題されていた問題らしいです！

難易度は 1457±8 で、C級としては平均的な難易度だと思います。

検索履歴 (paizaランク C 相当) を解いてみる

※ paiza レベルアップ問題集 スキルチェック過去問題セットより

問題

攻略ポイント

問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入しておきます。

INPUT1 = <<~"EOS"
  5
  book
  candy
  apple
  book
  candy
EOS
OUTPUT1 = <<~"EOS"
  candy
  book
  apple
EOS

INPUT2 = <<~"EOS"
  6
  apple
  book
  information
  note
  pen
  pineapple
"EOS"
OUTPUT2 = <<~"EOS"
  pineapple
  pen
  note
  information
  book
  apple
EOS

データを受け取れているかを確認するために下記のコードを書いて実行してみます。きちんと受け取れていれば確認用コードは削除します。

p INPUT1
p OUTPUT1
p INPUT2
p OUTPUT2
# > "5\nbook\ncandy\napple\nbook\ncandy\n"
# > "candy\nbook\napple\n"
# > "6\napple\nbook\ninformation\nnote\npen\npineapple\n"
# > "pineapple\npen\nnote\ninformation\nbook\napple\n"

次に問題を解くメソッド（ solve メソッドとします）を変数の下に書いていきます。
まずは、入力された文字列を改行で区切り、2行目以降の文字列を要素に持つ配列 search_words を作り、INPUT1を引数に与えて呼び出してみます。

def solve(input_lines)
  # 1行目は使わないので _ に代入して捨てる
  # 標準入力2行目以降を改行で分割して search_words に代入
  _, *search_words = input_lines.split("\n")

  # 動作確認用 search_words を返す
  search_words
end

p solve(INPUT1)
# > ["book", "candy", "apple", "book", "candy"]

search_words が正しく生成されていれば次の処理を書いていきます。

search_words の先頭から次々に要素を取り出し、問題で指示されたとおりに serch_history 配列を更新する処理を追記していきます。（戻り値を search_history に変更しているので注意して下さい。）

def solve(input_lines)
  # 標準入力2行目以降を search_words に代入
  _, *search_words = input_lines.split("\n")
  
  # search_history を初期化
  search_history = []
  
  # search_words の先頭から次々と要素を取り出す
  search_words.each do |search_word|
    # search_history に search_word が含まれていれば削除する
    search_history.delete(search_word)
    # search_history の 先頭に search_word を追加する
    search_history.unshift(search_word)
  end

  # search_history を返す
  search_history
end

p solve(INPUT1)
# > ["candy", "book", "apple"]

要素を改行で連結して、末尾に改行を追加したものを返すように変更し、動作を確認してみます。

def solve(input_lines)
  # 標準入力2行目以降を search_words に代入
  _, *search_words = input_lines.split("\n")
  
  # search_history を初期化
  search_history = []

  # search_words の先頭から次々と要素を取り出す
  search_words.each do |search_word|
    # search_history に search_word が含まれていれば削除する
    search_history.delete(search_word)
    # search_history の 先頭に search_word を追加する
    search_history.unshift(search_word)
  end

  # search_history を改行切りで連結して末尾に改行を付けて返す
  search_history.join("\n") << "\n"
end

p solve(INPUT1)
p solve(INPUT1) == OUTPUT1
puts solve(INPUT1)
# > "candy\nbook\napple\n"
# > true
# > candy
# > book
# > apple

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

解答コード

def solve(input_lines)
  # 標準入力2行目以降を search_words に代入
  _, *search_words = input_lines.split("\n")
  
  # search_history を初期化
  search_history = []
  
  # search_words の先頭から次々と要素を取り出す
  search_words.each do |search_word|
    # search_history に search_word が含まれていれば削除する
    search_history.delete(search_word)
    # search_history の 先頭に search_word を追加する
    search_history.unshift(search_word)
  end
  
  # search_history を改行切りで連結し末尾に改行を付けて返す
  search_history.join("\n") << "\n"
end

puts solve(STDIN.read)

他の解答例

reverse メソッドで serch_words 配列を前後逆にして、uniq メソッドで先に出現した単語を残して重複要素を取り除けば正解の配列を作ることが出来ます。

また、puts メソッドは自動的に配列の要素に改行して出力してくれるので、 join メソッドを使わずに配列をそのまま渡しても正解となります。

def solve(input_lines)
  _, *search_words = input_lines.split("\n")
  search_words.reverse.uniq
end

puts solve(STDIN.read)

1行にまとめると処理の流れが読みづらくなりますが、これでも正解となります。

puts STDIN.read.split("\n")[1..].reverse.uniq

今回のまとめ

delete メソッドで配列から要素を指定して削除、 unshift メソッドで配列の先頭に要素を挿入、これを繰り返すことで問題を解きました。

配列先頭への追加・削除（unshift・shift）と配列末尾への追加・削除（push・pop）はアルゴリズムを勉強していると頻繁に出てきます。データ構造のキューやスタックの話につながっていくので、セットで覚えておくと良いかもしれません！