paiza プログラミング

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

検索履歴

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

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

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

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

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

問題

あなたが利用しているブラウザでは検索ワードの履歴を見ることができません。あなたは検索ワードの履歴を見られないのは不便だと思ったので、検索ワードの履歴を見る機能を自分でつくることにしました。

検索ワードの履歴とは次のようにつくられます。

検索ワード W が以前に入力されたことがある場合:

  • 履歴中の W を削除する。
  • 履歴の先頭に W を追加する。

検索ワード W が以前に入力されたことがない場合:

  • 履歴の先頭に W を追加する。

検索ワード W が N 個与えられるので、N 個の検索ワードが与えられた後の履歴を表示するプログラムを書いてください。

入力される値

入力は以下のフォーマットで与えられます。

N
W_1
W_2
...
W_N

1 行目には検索ワードの数を表す整数 N が与えられます。
続く N 行では検索ワード W_i が与えられます。
続く N 行のうちの i 行目 (1 ≦ i ≦ N) には、検索ワード W_i が与えられます。検索ワード W_i は小文字のアルファベット a ~ z のみからなる文字列です。
入力は合計 N + 1 行であり、 最終行の末尾に改行が 1 つ入ります。

期待する出力

検索ワードを N 個入力した後の検索履歴を出力してください。
出力の最後に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

  • 1 ≦ N ≦ 100
  • 各 W_i (1 ≦ i ≦ N) に対して、W_iの文字数が20を超えない。

入力例1
5
book
candy
apple
book
candy
出力例1
candy
book
apple

入力例2
6
apple
book
information
note
pen
pineapple
出力例2
pineapple
pen
note
information
book
apple

攻略ポイント
問題を解く流れ

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

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)はアルゴリズムを勉強していると頻繁に出てきます。データ構造のキュースタックの話につながっていくので、セットで覚えておくと良いかもしれません!


【PR】アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。






通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。







通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。







通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者~中級者向けに書かれているので解説が非常に丁寧です。







Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


-paiza, プログラミング
-,

© 2024 じゃいごテック