문제
학생회 선거는 단순 다수결 방식입니다. 투표자는 후보 한 명의 이름을 적고, 가장 많은 표를 받은 후보가 당선됩니다. 후보 명단에 없는 이름(오타나 명단 외 인물)에 던진 표는 무효입니다. 최다 득표가 여러 명이면 모두 당선되어 직무를 함께 맡습니다.
plurality_election(candidates, votes) 함수를 구현하세요.
입력
candidates: 후보들의 이름이며, 모두 서로 다릅니다.
votes: 투표자 한 명당 이름 하나입니다. 이름은 대소문자까지 정확히 일치해야 합니다.
출력
당선자 이름을 모두 candidates에 나온 순서대로 반환하세요. 유효표가 하나도 없으면 모든 후보가 0표로 동률이므로 전원을 반환합니다.
제약 조건
1 ≤ candidates의 길이 ≤ 20
0 ≤ votes의 길이 ≤ 1000
이름은 1~20개의 ASCII 영문자로 이루어집니다
예시
입력:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Ben", "Ava", "Ben", "Cruz", "Ben"]
예상 출력:
expected = ["Ben"]
입력:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Ben", "Ava", "Ben", "Cruz", "Ben"};
예상 출력:
std::vector<std::string> expected = {"Ben"};
입력:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Ben", "Ava", "Ben", "Cruz", "Ben"};
예상 출력:
string[] expected = new string[] {"Ben"};
설명
Ben이 3표로 각각 1표인 Ava와 Cruz보다 많으므로 ["Ben"]입니다.
입력:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Cruz", "Ava", "ava", "Dana"]
예상 출력:
expected = ["Ava", "Cruz"]
입력:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Cruz", "Ava", "ava", "Dana"};
예상 출력:
std::vector<std::string> expected = {"Ava", "Cruz"};
입력:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Cruz", "Ava", "ava", "Dana"};
예상 출력:
string[] expected = new string[] {"Ava", "Cruz"};
설명
ava와 Dana는 무효표이므로 Ava와 Cruz가 1표씩 동률이 되어 ["Ava", "Cruz"]입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
모든 후보를 0표로 시작해야 표를 못 받은 후보도 셀 수 있습니다.
힌트 2
이름이 후보와 정확히 같을 때만 표로 세세요.
힌트 3
먼저 최다 득표수를 찾은 다음, 그 득표수의 후보를 명단 순서대로 모으세요.
예상 복잡도
시간 O(c + v), 추가 공간 O(c)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.