#3/20 Hash Tables: Ransom Note [hacker rank / Cracking the Coding Interview Challenges]

hackerrank code interview

#3 Hash Tables: Ransom Note

www.hackerrank.com

3行の入力が与えられる。

  • 1行目: スペース区切りで、magazineの単語数、ransom note の単語数がそれぞれ数値で指定。
  • 2行目: magazine の単語がスペース区切り
  • 3行目: ransom note の単語がスペース区切り

上記の入力から、magazine の単語の集合を使ってransom noteの単語の集合を複製することができれば、"Yes" を出力、それ以外の場合は、"No" を出力する。

解

l1, l2, l3 = $stdin.read.split("\n")
m, n = l1.split(" ").map(&:to_i)
magazine, ransom = l2.split(" ").sort, l3.split(" ").sort

ransom.each do |v|
    i = magazine.index(v)
    if !i
        puts "No"
        exit
    end
    magazine.delete_at(i)
end
puts "Yes"

github.com

まとめ

単純にransom note の単語を1つずつ magazine 内の単語と照会、ヒットしたらmagazineから当該単語を削除して次の単語へ、ヒットしなければ、No を出力しプログラムを終了する。 ruby の index は配列の頭から検索するため、 最初にmagazine, ransom noteの単語配列を予めsortしておくことで検索を高速化した。