C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

English Sentence|AOJ| Volume0-0029

単語の出現頻度 | Aizu Online Judge を解きました。

題意:

・英文が与えられるので、「出現頻度が最も高い単語」と、「文字数が最も多い単語」を出力する。
・与えられる英文は半角英文字で、半角スペースを含む。
・文章の文字数は1000文字以下
・一つの単語の文字数は32文字以下
・「出現頻度が最も高い単語」「最長の文字数を持つ単語」はそれぞれ文中に一つだけしか存在しない事が保証されている。

考察:

<出現頻度が最も高い単語>
出現頻度が最も高い = 重複数が最も多い と言えるので、各単語の重複数のMAX値をとる。
➡︎ 指定された値と等値な要素の数を数える事ができる std::count *1 を使う。

<文字数が最も多い単語>
文字数が最も多い = 文字列長(要素数)が最も長い(多い) と言えるので、各単語の文字列長のMAX値をとる。
➡︎ 文字列長は string::size *2 で取得する。

計算量:

入力の受け取りに Θ( |S| ) 時間、vector への要素構築に償却定数時間、MAX値を探索するloopに O( |S| ) 時間, std::count で 1つの単語について重複を数えるのに  O(|S|) 回なので、1回の loop で O( |S|^2 ) 時間となり、全体では O( |S|^2 ) 時間。

コード:


提出はここ

復習:

プロの提出を見ていたら map解 があったので、 mapでも解いてみました。
値の持ち方を map< 単語, 重複数 > として、重複を始めにカウントしてしまうという解き方。
計算量は、全体で O( N\, log \,N ) なので、こちらの方が良さそう。

追記:

( int ) とキャストしている箇所を size_t にしたら?とアドバイス頂いたので、修正してみました。

無駄なキャストがなくなりました!