문제
In an instant runoff election, every voter ranks all the candidates. The count goes in rounds:
- Each ballot counts as one vote for its highest-ranked candidate who is still in the race.
- If a candidate has more than half of all ballots, that candidate wins.
- Otherwise, if every remaining candidate has the same number of votes, they are all tied and the election ends.
- Otherwise, every remaining candidate with the fewest votes is eliminated (all of them at once if several share the lowest count), and a new round starts.
Implement runoff_election(candidates, ballots).
Input
candidates: The candidates' names. Candidate i is candidates[i].
ballots: One row per voter: the candidate numbers (0-based) from most preferred to least preferred. Each row lists every candidate exactly once.
Output
Return a list with the winner's name, or, if the election ends in a tie, the names of all tied candidates in the order they appear in candidates. With no ballots, all candidates are tied.
제약 조건
1 ≤ length of candidates ≤ 9
0 ≤ number of ballots ≤ 200
예시
입력:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
예상 출력:
expected = ["Ana"]
입력:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 2, 1},
{1, 2, 0},
{1, 0, 2},
{2, 0, 1}
};
예상 출력:
std::vector<std::string> expected = {"Ana"};
입력:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 2, 1},
new long[] {1, 2, 0},
new long[] {1, 0, 2},
new long[] {2, 0, 1}
};
예상 출력:
string[] expected = new string[] {"Ana"};
설명
Round 1: Ana 2, Bo 2, Cy 1; nobody has more than 2.5, so Cy is out. Cy's ballot moves to Ana, who wins with 3 of 5: ["Ana"].
입력:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
예상 출력:
expected = ["Ana", "Bo", "Cy"]
입력:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 1, 2},
{1, 2, 0},
{1, 2, 0},
{2, 1, 0},
{2, 1, 0}
};
예상 출력:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
입력:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {1, 2, 0},
new long[] {1, 2, 0},
new long[] {2, 1, 0},
new long[] {2, 1, 0}
};
예상 출력:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
설명
Every candidate has 2 first-place votes out of 6, so the three of them are tied: ["Ana", "Bo", "Cy"].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
Keep a true/false list of who is still in the race and recount from scratch every round.
힌트 2
A majority means votes × 2 greater than the number of ballots.
힌트 3
Find the lowest count among remaining candidates only; if everyone remaining has it, the election is a tie.
예상 복잡도
O(c^2 × b) time, O(c) extra space
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.