BOJ 24776 - Recount

문제 링크

문제#

The recent schoolboard elections were hotly contested: a proposal to swap school start times for elementary and high school students, a controversial new dress code proposal that bans athletic clothes in school, and a proposal to raise real-estate taxes to pay for a new football practice facility, and the list goes on and on. It is now hours after the polls have closed and a winner has yet to emerge!

In their desperation, the election officials turn to you and ask you to write a program to count the vote!

입력#

The input consists of a single test case, which is a list of votes cast. Each line in the input contains the name of a candidate for whom a vote was cast. A name may consist of multiple words, separated by spaces. Words contain letters or hyphens, but no other punctuation characters. There will be at least 2 votes on the list. The list of votes ends with a single line containing the characters ***. This line should not be counted. There can be up to $100,000$ valid votes.

출력#

If a candidate obtained a simple or absolute majority of all votes cast (that is, more than any other candidate), output the name of this candidate! If no candidate obtained a simple majority, output: "Runoff!" (don't forget to include the exclamation mark!)

풀이#

후보 이름이 여러 줄로 들어오고, 마지막 ***에서 입력이 끝난다. 가장 많이 나온 이름이 하나뿐이면 그 후보가 당선이고, 최다 득표자가 둘 이상이면 Runoff!를 출력하면 된다.

코드에서는 map<string, int>로 후보별 득표 수를 세면서 현재 최대 득표 수 max_cnt를 갱신한다. 입력이 끝난 뒤 모든 후보를 훑으며 max_cnt와 같은 후보가 몇 명인지 확인한다.

최다 득표 후보를 처음 만나면 답으로 저장하고, 같은 득표 수 후보를 또 만나면 즉시 결선 상황으로 판단한다.

코드#

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
 
static string LAST_WORD = "***";
map<string, int> m;
string s;
int max_cnt;
 
string solve() {
	string ans = "";
	for (auto& itr : m) {
		if (itr.second == max_cnt) {
			if (ans.empty()) ans = itr.first;
			else return "Runoff!";
		}
	}
 
	return ans;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	while(getline(cin, s) && s != LAST_WORD) {
		m[s]++;
		max_cnt = max(max_cnt, m[s]);
	}
 
	cout << solve() << '\n';
	return 0;
}

복잡도#

• 시간 복잡도: 후보 수를 $N$이라 하면 map 연산 기준 $O(N \log N)$이다.
• 공간 복잡도: 후보별 득표 수를 저장하므로 $O(N)$이다.

마무리#

Recount는 득표 수 자체보다 최다 득표자가 유일한지가 핵심이다. 빈도를 센 뒤 같은 최댓값을 가진 후보가 또 있는지만 확인하면 결선 여부가 결정된다.