【Python】優先順位付き投票から最終ランキングを上位順に求めるプログラム

問題の概要

文字列のリスト votes が与えられます。各要素は小文字のみで構成され、候補者への投票を「最も優先度が高い順位から低い順位へ」の順に表しています。候補者の順位は、まず第1優先として受け取った票数で決まります。ここで同点が発生した場合は、次に高い優先度での得票数を比較し、それでも決まらない場合はアルファベット順で順位を確定します。このルールに基づき、チーム（候補者）の最終ランキングを上位から下位の順に出力します。

入力例と考え方

たとえば votes = ["zyx", "zxy", "xyz"] の場合、出力は "zxy" になります。

• 「z」は第1優先の票を最も多く獲得したため1位。
• 「x」は第1優先の票数が2番目に多い。
• 「y」は第1優先の票を1票も得られなかったため最下位。

解法のアプローチ

以下の手順で問題を解きます。

1. count := votes 内の文字列の長さ（＝候補者の総数）
2. cand := 空のマップ。キーごとに長さ count のリスト（初期値はすべて0）を保持する
3. votes の各要素 v について処理を行う：
   • v の各インデックス i と文字 c に対し、cand[c][i] を1増やす
4. cand の各項目を得票数の降順でソートする。値が同じ場合はアルファベット順に並べる
5. ソート済みの要素を連結して文字列として返す

実装例

from collections import defaultdict
class Solution:
    def solve(self, votes):
        count = len(votes[0])
        cand = defaultdict(lambda: [0] * count)
        for v in votes:
            for i, c in enumerate(v):
                cand[c][i] += 1
        return "".join(sorted(cand.keys(), key=lambda x: (cand[x], -ord(x)), reverse=True))
    
ob = Solution()
votes = ["zyx", "zxy", "xyz"]
print(ob.solve(votes))

入力

["zyx", "zxy", "xyz"]

出力

zxy

コードのポイント

ソートのキーには (cand[x], -ord(x)) を指定し、reverse=True で降順ソートしています。Pythonではリスト同士を比較すると要素を先頭から順に比較するため、第1優先・第2優先…という優先順位付けが自然に実現できます。また、同点の場合は -ord(x) が大きい方（＝文字コードが小さい、つまりアルファベットで早い文字）が先に来るようになっているため、「同点ならアルファベット順」という条件も満たされます。

計算量

有権者数を n、候補者数を m とすると、集計には O(n × m)、ソートにはキー比較としてリスト比較が含まれるため O(m² log m) かかります。ただし候補者数はアルファベット26文字に制限されるため、実用上は非常に高速に動作します。