모든 챌린지
보통 0명 해결 정답률 0%

즉석 결선 투표

순위 투표용지로 즉석 결선 투표를 진행하며, 라운드마다 가장 약한 후보를 탈락시킵니다.

배우게 될 내용

  • 각 투표용지를 남은 후보 중 1순위에게 계산한다
  • 과반 당선자와 전원 동률을 판별한다
  • 최소 득표 후보를 모두 탈락시킨다

문제

원문 보기 (영어)

즉석 결선 투표에서는 모든 투표자가 전체 후보에게 순위를 매깁니다. 개표는 라운드 단위로 진행됩니다.

  1. 각 투표용지는 아직 탈락하지 않은 후보 중 순위가 가장 높은 후보에게 1표로 계산됩니다.
  2. 어떤 후보가 전체 투표용지의 과반을 넘게 얻으면 그 후보가 당선됩니다.
  3. 그렇지 않고 남은 후보가 모두 같은 표를 얻었다면 전원 동률로 선거가 끝납니다.
  4. 그렇지 않으면 남은 후보 중 표가 가장 적은 후보를 모두 탈락시키고(최소 득표가 여러 명이면 한꺼번에) 새 라운드를 시작합니다.

runoff_election(candidates, ballots) 함수를 구현하세요.

입력

candidates: 후보들의 이름입니다. i번 후보는 candidates[i]입니다.

ballots: 투표자 한 명당 한 행으로, 가장 선호하는 후보부터 가장 덜 선호하는 후보까지의 후보 번호(0부터 시작)입니다. 각 행에는 모든 후보가 정확히 한 번씩 나옵니다.

출력

당선자 이름 하나가 든 리스트를 반환하세요. 동률로 끝났다면 동률인 후보 전원의 이름을 candidates에 나온 순서대로 반환합니다. 투표용지가 없으면 모든 후보가 동률입니다.

제약 조건

1 ≤ candidates의 길이 ≤ 9

0 ≤ 투표용지 수 ≤ 200

예시

예시 1
입력:
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"]입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.