이 튜토리얼에서는 선거의 최종 승자를 찾아내는 C++ 프로그램을 작성해 보겠습니다. 각 후보가 선거에서 받은 득표 정보가 문자열 배열로 주어지며, 이를 집계해 가장 많은 표를 얻은 후보를 가려내야 합니다. 먼저 예시부터 살펴보겠습니다.
입력
{"A", "B", "C", "B", "A", "C", "D", "D", "A", "B", "D", "B", "A"}
출력
A
위 예시에서 A와 B는 각각 4표로 동률을 이루고 있습니다. 이처럼 두 후보의 득표 수가 같을 때는 이름을 알파벳 순서로 비교하여 사전순으로 앞선 후보를 승자로 선택해야 합니다.
해결 접근 방법
더미 데이터로 문자열 배열을 초기화합니다.
후보 이름을 키(key)로, 득표 수를 값(value)으로 저장하는 맵(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;
}
코드 설명
candidate_votes_count[votes[i]]++ 구문이 핵심입니다. C++의 std::map은 존재하지 않는 키에 접근하면 해당 키를 값 0으로 자동 생성하므로, 한 줄만으로 득표 수를 손쉽게 누적할 수 있습니다.
또한 std::map은 키를 오름차순(사전순)으로 정렬해 저장하기 때문에 맵을 순회하면 항상 알파벳 순서대로 후보를 만나게 됩니다. 따라서 득표 수가 같은 후보가 여러 명이더라도 가장 먼저 발견된, 즉 사전순으로 앞선 후보가 자연스럽게 승자로 유지됩니다.
성능 측면에서 보면, 득표 배열의 길이를 n이라 할 때 맵 삽입 연산으로 인해 시간 복잡도는 O(n log n)이 되며, 공간 복잡도는 후보 수에 비례합니다.
실행 결과
위 프로그램을 컴파일해 실행하면 다음과 같은 결과가 출력됩니다.
A
마무리
지금까지 맵을 활용해 선거 승자를 찾는 방법을 알아보았습니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.