はじめに
現在積み上げ学習の一環として、paizaのレベルアップ問題に取り組んでいます。
今回は、連想配列に対してソートをするという実装につまづいたので備忘録としてまとめて見ます。
問題内容
問題内容は以下のとおりです。
文字と整数の組のソート
「1行目に行数を表す整数 n、続く n 行の各行で「文字」と「整数」の組が空白区切りで入力されます。
n 個の組について、「文字」の値が同じ組同士の数値を足しあわせてまとめ、まとめた数値の降順で、文字とまとめた数値の組を出力してください。
この際、まとめた数値は重複しません。」
入力例
7
A 1
D 6
C 2
G 4
B 70
A 10
B 5
出力例
B 75
A 11
D 6
G 4
C 2
問題文は以上です。
簡単に要約すると
「入力された値を、降順で並べ替える。(同じ文字の場合は数値を加算する)」という問題です。
つまづいてしまった要因
今回つまづいてしまった大きな要因としては、連想配列について知識が足りていなかったからです。
具体的には
・連想配列についての知識(格納の仕方、加算の仕方、条件指定の仕方など)
・連想配列に対してのsortメソッドの使い方
・連想配列に対してのeach文の回し方。
などです。
またアルゴリズム問題への場数の少なさも大いに関係してると思います。
回答例
回答の方針としては、
①連想配列を作る
②入力された回数分繰り返し処理を行う
③keyとvalueで値を分ける
④条件分を作って連想配列に入れていく。
もしもvalueが一緒なら、keyを加算する。
⑤sort_byメソッドとreverseメソッドで降順に並べ替える
⑥ソートした連想配列をeach文で出力する
という流れです。
以下が回答例です。
count = gets.to_i
array = {}
count.times do |i|
str = gets.split
string = str[0]
points = str[1].to_i
if array[string]
array[string] = array[string] + points
else
array[string] = points
end
end
array = array.sort_by{|_,v| v }.reverse
array.each do |key,value|
puts "#{key} #{value}"
end
学んだこと① 連想配列の基本
連想配列の基本的な仕組みについて学びました
・array[key] = value で値を入力
・if array[key] という書き方でkeyが重複しているかをチェックできる
・繰り返し処理をする場合は|key,value|という形で値を取り出せる
参考文献
https://www.javadrive.jp/ruby/hash/index7.html
学んだこと② sort_byメソッド
・sortメソッドで昇順、sort.reverseで降順になる
・keyに対して降順でソートしたい時はsort_byメソッドを以下の形式で使う
array.sort_by{|_,v| v }.reverse
参考文献
https://blog.toshimaru.net/ruby-hash-sort/
編集リクエスト リファクタリングに挑戦(2/6追記)
編集リクエストを頂いたのでリファクタリングに挑戦しました!
①変数名の修正
今回はハッシュを使っているため、
arrayという変数ではなくそれぞれhashという変数名に変更しました。
②if文を簡略化
ハッシュに初期値を指定することでif文を削除できる
まずはハッシュを作るときに初期値を指定します。
hash = {}
↓↓
hash = Hash.new(0)
そして繰り返し処理の中のif文を以下のように修正します。
if array[string]
array[string] = array[string] + points
else
array[string] = points
end
↓↓
hash[string] += points
5行あったコードが1行になりました!
③sort_byメソッド
符号反転を使って簡略化
array.sort_by{|_,v| v }.reverse
↓↓
array.sort_by{|_,v| -v }
修正したコードの全体
結果以下のように修正できました!
count = gets.to_i
hash = Hash.new(0)
count.times do |i|
str = gets.split
string = str[0]
points = str[1].to_i
hash[string] += points
end
hash = hash.sort_by{|_,v| -v }
hash.each do |key,value|
puts "#{key} #{value}"
end
ひと工夫でこんなにも、コードが効率的になるってすごい。
編集依頼ありがとうございました!
まとめ
今回はつまづいてしまった、paizaのアルゴリズム問題についてまとめてみました。
思った事は、rubyの基本知識をもっと定着する必要がある事。
アルゴリズム問題にもっと慣れる事。
が必要だという事です。
今後も継続して勉強していきます。