문제
즉석 결선 투표에서는 모든 투표자가 전체 후보에게 순위를 매깁니다. 개표는 라운드 단위로 진행됩니다.
- 각 투표용지는 아직 탈락하지 않은 후보 중 순위가 가장 높은 후보에게 1표로 계산됩니다.
- 어떤 후보가 전체 투표용지의 과반을 넘게 얻으면 그 후보가 당선됩니다.
- 그렇지 않고 남은 후보가 모두 같은 표를 얻었다면 전원 동률로 선거가 끝납니다.
- 그렇지 않으면 남은 후보 중 표가 가장 적은 후보를 모두 탈락시키고(최소 득표가 여러 명이면 한꺼번에) 새 라운드를 시작합니다.
runoff_election(candidates, ballots) 함수를 구현하세요.
입력
candidates: 후보들의 이름입니다. i번 후보는 candidates[i]입니다.
ballots: 투표자 한 명당 한 행으로, 가장 선호하는 후보부터 가장 덜 선호하는 후보까지의 후보 번호(0부터 시작)입니다. 각 행에는 모든 후보가 정확히 한 번씩 나옵니다.
출력
당선자 이름 하나가 든 리스트를 반환하세요. 동률로 끝났다면 동률인 후보 전원의 이름을 candidates에 나온 순서대로 반환합니다. 투표용지가 없으면 모든 후보가 동률입니다.
제약 조건
1 ≤ candidates의 길이 ≤ 9
0 ≤ 투표용지 수 ≤ 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"};
설명
1라운드는 Ana 2표, Bo 2표, Cy 1표입니다. 2.5표를 넘은 후보가 없으므로 Cy가 탈락합니다. Cy의 표가 Ana에게 넘어가 Ana가 5표 중 3표로 당선되므로 ["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"};
설명
6표 중 모든 후보가 1순위 표를 2표씩 받았으므로 세 후보 모두 동률입니다. 결과는 ["Ana", "Bo", "Cy"]입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
아직 남아 있는 후보를 참/거짓 리스트로 관리하고, 라운드마다 처음부터 다시 세세요.
힌트 2
과반이란 득표수 × 2가 투표용지 수보다 큰 것입니다.
힌트 3
최소 득표수는 남은 후보 중에서만 찾으세요. 남은 후보 모두가 그 득표수라면 동률입니다.
예상 복잡도
시간 O(c^2 × b), 추가 공간 O(c)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.