問題
生徒会選挙は単純な相対多数で決まります。投票者はそれぞれ候補者1人の名前を書き、最も多く票を集めた候補者が当選です。候補者リストにない名前(書き間違いや、立候補していない人の名前)への票は無効になります。最多得票数で並んだ候補者が複数いる場合は、全員が当選して役職を分け合います。
plurality_election(candidates, votes) を実装してください。
入力
candidates: 候補者の名前。すべて異なります。
votes: 投票者1人につき1つの名前。大文字と小文字も含めて完全に一致する必要があります。
出力
当選者全員の名前を、candidates に現れる順に返してください。有効票が1票もなければ、全候補者が0票で並ぶので全員を返します。
制約
1 ≤ candidates の長さ ≤ 20
0 ≤ votes の長さ ≤ 1000
名前は1から20文字の ASCII 英字
例
入力:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Ben", "Ava", "Ben", "Cruz", "Ben"]
期待される出力:
expected = ["Ben"]
入力:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Ben", "Ava", "Ben", "Cruz", "Ben"};
期待される出力:
std::vector<std::string> expected = {"Ben"};
入力:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Ben", "Ava", "Ben", "Cruz", "Ben"};
期待される出力:
string[] expected = new string[] {"Ben"};
解説
Ben は3票で、1票ずつの Ava と Cruz より多いので ["Ben"] です。
入力:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Cruz", "Ava", "ava", "Dana"]
期待される出力:
expected = ["Ava", "Cruz"]
入力:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Cruz", "Ava", "ava", "Dana"};
期待される出力:
std::vector<std::string> expected = {"Ava", "Cruz"};
入力:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Cruz", "Ava", "ava", "Dana"};
期待される出力:
string[] expected = new string[] {"Ava", "Cruz"};
解説
ava と Dana は無効になり、Ava と Cruz が1票ずつで並びます。結果は ["Ava", "Cruz"] です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
票のない候補者も数に入るように、全候補者を0票から始めましょう。
ヒント 2
名前が候補者と完全に一致するときだけ票を数えます。
ヒント 3
まず最多得票数を求め、その票数の候補者をリストの順に集めましょう。
目安の計算量
時間 O(c + v)、追加メモリ O(c)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。