【C++入門】投票データから選挙の当選者を見つける方法

はじめに

このチュートリアルでは、選挙の当選者（勝者）を見つけるプログラムをC++で作成します。各候補者が獲得した票が文字列の配列として与えられ、その中から最も多く票を獲得した候補者の名前を出力します。

まずは、具体的な例を見てみましょう。

入力例

{"A", "B", "C", "B", "A", "C", "D", "D", "A", "B", "D", "B", "A"}

出力例

A

この例では、AとBが同じ票数を獲得しています。このような場合、名前のアルファベット順に基づいて当選者を決定する必要があります。アルファベット順で先に来る「A」が当選者となります。

解決の手順

それでは、この問題を解くための手順を確認しましょう。

• ダミーデータを含む文字列型の配列を初期化します。

• キーを string 型、値を int 型とするマップ（std::map）を用意します。

• 投票データの配列を走査し、各候補者の得票数をカウントしてマップに格納します。

• 得票数が集計できたら、マップを走査して最大得票数を持つキー（候補者名）を探します。

• 複数の候補者が同票の場合は、名前を比較してアルファベット順で先の候補者を選びます。

• 当選者を出力します。

サンプルコード

実際のコードを見てみましょう。

#include "bits/stdc++.h"
using namespace std;
void findElectionWinner(string votes[], int total_votes) {
    map<string, int> candidate_votes_count;
    // 各候補者の得票数をカウント
    for (int i = 0; i < total_votes; i++) {
        candidate_votes_count[votes[i]]++;
    }
    // 当選者を検索
    int max_votes = 0;
    string election_winner;
    for (auto& entry : candidate_votes_count) {
        string key = entry.first;
        int val = entry.second;
        // 最大得票数との比較
        if (val > max_votes) {
            // 最大得票数と当選者を更新
            max_votes = val;
            election_winner = key;
        }
        // 同票の場合は名前を比較
        else if (val == max_votes && election_winner > key) {
            election_winner = key;
        }
    }
    cout << election_winner << endl;
}
int main() {
    string votes[] = {"A", "B", "C", "B", "A", "C", "D", "D", "A", "B", "D", "B", "A"};
    findElectionWinner(votes, 13);
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が出力されます。

A

コードの解説

ここでは、プログラムのポイントを簡単に整理しておきましょう。

• 得票数の集計： candidate_votes_count[votes[i]]++ のように書くことで、キーが存在しない場合は自動的に0で初期化され、1ずつ加算されていきます。これにより、簡潔に票数を数えられます。

• 同票時の処理： election_winner > key という条件により、現在の当選者候補よりも辞書順（アルファベット順）で小さい名前が見つかった場合に、当選者を入れ替えています。

• マップの特性： std::map はキーを自動的にソートして保持するため、要素を走査すると名前の昇順で処理されます。この特性も、同票時の判定をシンプルにする助けになります。

なお、計算量は投票データの走査に O(n)、マップへの挿入・参照に O(log m)（mは候補者数）となるため、全体として効率的に動作します。

まとめ

今回は、std::map を活用して各候補者の得票数を集計し、最多得票者を選挙の当選者として求める方法を学びました。同票の場合には名前のアルファベット順で優劣をつけるというルールも、比較演算子を使えば簡単に実装できることが分かりました。

このチュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。