후보 c명을 두고 투표지 v장을 모았다. 투표지에는 마음에 드는 차례대로 후보 이름이 1명 이상 적혀 있고, 모든 후보를 다 적을 필요는 없다. 첫 줄에 c와 v가, 둘째 줄에 후보 이름 c개가 빈칸 하나씩으로 나뉘어 주어진다. 다음 v줄에 투표지가 한 장씩 주어진다. 처음에는 모든 후보가 남아 있고, 다음 셈을 판마다 되풀이한다.
1. 투표지마다, 그 투표지에 적힌 이름 가운데 아직 남은 후보로서 가장 앞에 적힌 후보에게 한 표를 준다. 남은 후보가 하나도 적혀 있지 않은 투표지는 다 쓴 투표지라서 이번 판에 세지 않는다.
2. 남은 후보마다 "이름:표수"를 둘째 줄의 차례대로 빈칸 하나씩 띄워 한 줄에 출력한다. 표가 없는 후보도 "이름:0"으로 출력한다.
3. 어떤 후보의 표수가 이번 판에 센 투표지 수의 절반보다 많으면(딱 절반은 아니다), 또는 남은 후보가 한 명뿐이면 그 후보가 당선이다. 다음 줄에 당선자 이름을 출력하고 끝낸다.
4. 아니면 표가 가장 적은 후보 한 명을 떨어뜨리고 다음 판으로 간다. 표가 가장 적은 후보가 여럿이면 그 가운데 둘째 줄에서 가장 뒤에 적힌 후보를 떨어뜨린다.
입력
1 ≤ c ≤ 20, 1 ≤ v ≤ 1000. 후보 이름은 영어 소문자·숫자 1 ~ 10글자이고 서로 다르다. 투표지 한 장에는 서로 다른 후보 이름이 1 ~ c개 빈칸 하나씩으로 나뉘어 적혀 있다
출력
판마다 "이름:표수" 한 줄, 마지막 줄에 당선자 이름
예시 1 · stdin
4 9
kim lee park choi
kim lee
kim
lee park
lee kim
park lee
park
choi park
choi
kim park
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
판마다 사전으로 표를 세고, 다 쓰지 않은 투표지 수도 따로 세고, 이름이 남은 후보 목록에 있는지 물어요. 셈 사전은 남은 후보를 모두 0으로 먼저 넣어 두는 게 요점이에요: Python {name: 0 for name in remaining}, JS·TS new Map(remaining.map(name => [name, 0])), Java put(name, 0) 뒤 merge(name, 1, Integer::sum), C# remaining.ToDictionary(name => name, name => 0), C++ std::mapvotes[name] = 0, 크레이콘 votes[name] = 0;(사전()). C는 후보 번호마다 칸을 둔 배열 int votes[20] = {0}이에요. 함정 하나: Python Counter()로 받은 표만 세면 0표 후보는 사전에 들어가지 않아요. votes[name]은 없는 이름에 0을 줘서 줄은 맞게 나오지만, min(votes.values())가 0을 놓쳐서 0표 후보 대신 엉뚱한 후보를 떨어뜨려요. 목록에 있나는 Python in, JS·TS includes, Java contains, C# Contains, C++ std::find(...) != end(), 크레이콘 있나예요. 함정 둘: Java Map<String, Integer>의 값은 Integer 상자라, fewest도 Integer로 두면 votes.get(a) == fewest는 같은 상자인지 비교해요. -128 ~ 127은 미리 만든 상자를 같이 써서 맞는 듯 보이지만, 128표 이상인 동점은 놓쳐요. int로 꺼내 비교하거나 equals를 써요. 함정 셋: 과반의 밑수는 투표지 전체가 아니라 이번 판에 센 투표지 수이고, 딱 절반은 과반이 아니라서 2 * 표 > 센 수예요.
Pythonmain.py · 25 줄
import syslines = sys.stdin.read().split("\n")c, v = map(int, lines[0].split())remaining = lines[1].split() # 남은 후보, 처음 적힌 차례대로ballots = [lines[2 + i].split() for i in range(v)]while True: votes = {name: 0 for name in remaining} # 0표인 후보도 먼저 넣어 둔다 active = 0 # 남은 후보를 하나라도 적은 투표지 수 for ballot in ballots: for name in ballot: if name in remaining: # 이 투표지에서 가장 앞에 적힌 남은 후보 votes[name] += 1 active += 1 break print(" ".join(f"{name}:{votes[name]}" for name in remaining)) leader = max(remaining, key=lambda name: votes[name]) if 2 * votes[leader] > active or len(remaining) == 1: print(leader) break fewest = min(votes.values()) loser = [name for name in remaining if votes[name] == fewest][-1] # 동점이면 뒤에 적힌 후보 remaining.remove(loser)
JavaScriptmain.js · 29 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [c, v] = lines[0].trim().split(" ").map(Number);const remaining = lines[1].trim().split(" "); // 남은 후보, 처음 적힌 차례대로const ballots = lines.slice(2, 2 + v).map((line) => line.trim().split(" "));const out = [];while (true) { const votes = new Map(remaining.map((name) => [name, 0])); // 0표인 후보도 먼저 넣어 둔다 let active = 0; // 남은 후보를 하나라도 적은 투표지 수 for (const ballot of ballots) { const first = ballot.find((name) => remaining.includes(name)); // 가장 앞에 적힌 남은 후보 if (first !== undefined) { votes.set(first, votes.get(first) + 1); active++; } } out.push(remaining.map((name) => `${name}:${votes.get(name)}`).join(" ")); const count = (name) => votes.get(name); const best = Math.max(...remaining.map(count)); if (2 * best > active || remaining.length === 1) { out.push(remaining.find((name) => count(name) === best)); break; } const fewest = Math.min(...remaining.map(count)); const loser = remaining.filter((name) => count(name) === fewest).pop(); // 동점이면 뒤에 적힌 후보 remaining.splice(remaining.indexOf(loser), 1);}console.log(out.join("\n"));
TypeScriptmain.ts · 30 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [c, v] = lines[0].trim().split(" ").map(Number);const remaining: string[] = lines[1].trim().split(" "); // 남은 후보, 처음 적힌 차례대로const ballots: string[][] = lines.slice(2, 2 + v).map((line) => line.trim().split(" "));const out: string[] = [];while (true) { const votes = new Map<string, number>(remaining.map((name): [string, number] => [name, 0])); // 0표인 후보도 먼저 넣어 둔다 let active = 0; // 남은 후보를 하나라도 적은 투표지 수 for (const ballot of ballots) { const first = ballot.find((name) => remaining.includes(name)); // 가장 앞에 적힌 남은 후보 if (first !== undefined) { votes.set(first, (votes.get(first) ?? 0) + 1); active++; } } const count = (name: string): number => votes.get(name) ?? 0; out.push(remaining.map((name) => `${name}:${count(name)}`).join(" ")); const best = Math.max(...remaining.map(count)); if (2 * best > active || remaining.length === 1) { out.push(remaining.find((name) => count(name) === best) ?? ""); break; } const fewest = Math.min(...remaining.map(count)); const tied = remaining.filter((name) => count(name) === fewest); remaining.splice(remaining.indexOf(tied[tied.length - 1]), 1); // 동점이면 뒤에 적힌 후보}console.log(out.join("\n"));
JavaMain.java · 47 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().trim().split(" "); int v = Integer.parseInt(first[1]); List<String> remaining = new ArrayList<>(Arrays.asList(br.readLine().trim().split(" "))); // 처음 적힌 차례대로 List<String[]> ballots = new ArrayList<>(); for (int i = 0; i < v; i++) ballots.add(br.readLine().trim().split(" ")); StringBuilder out = new StringBuilder(); while (true) { Map<String, Integer> votes = new HashMap<>(); for (String name : remaining) votes.put(name, 0); // 0표인 후보도 먼저 넣어 둔다 int active = 0; // 남은 후보를 하나라도 적은 투표지 수 for (String[] ballot : ballots) { for (String name : ballot) { if (remaining.contains(name)) { // 가장 앞에 적힌 남은 후보 votes.merge(name, 1, Integer::sum); active++; break; } } } StringJoiner line = new StringJoiner(" "); for (String name : remaining) line.add(name + ":" + votes.get(name)); out.append(line).append('\n'); // Integer 상자끼리 ==로 비교하지 않도록 int로 꺼내 둔다 int best = -1, fewest = Integer.MAX_VALUE; String leader = "", loser = ""; for (String name : remaining) { int n = votes.get(name); if (n > best) { best = n; leader = name; } if (n <= fewest) { fewest = n; loser = name; } // <=: 동점이면 뒤에 적힌 후보 } if (2 * best > active || remaining.size() == 1) { out.append(leader).append('\n'); break; } remaining.remove(loser); } System.out.print(out); }}
C#Main.cs · 42 줄
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { int v = int.Parse(Console.ReadLine().Trim().Split(' ')[1]); var remaining = Console.ReadLine().Trim().Split(' ').ToList(); // 처음 적힌 차례대로 var ballots = new List<string[]>(); for (int i = 0; i < v; i++) ballots.Add(Console.ReadLine().Trim().Split(' ')); var sb = new StringBuilder(); while (true) { var votes = remaining.ToDictionary(name => name, name => 0); // 0표인 후보도 먼저 넣어 둔다 int active = 0; // 남은 후보를 하나라도 적은 투표지 수 foreach (string[] ballot in ballots) { string first = ballot.FirstOrDefault(name => remaining.Contains(name)); // 가장 앞에 적힌 남은 후보 if (first != null) { votes[first]++; active++; } } sb.Append(string.Join(" ", remaining.Select(name => $"{name}:{votes[name]}"))).Append('\n'); int best = remaining.Max(name => votes[name]); if (2 * best > active || remaining.Count == 1) { sb.Append(remaining.First(name => votes[name] == best)).Append('\n'); break; } int fewest = remaining.Min(name => votes[name]); remaining.Remove(remaining.Last(name => votes[name] == fewest)); // 동점이면 뒤에 적힌 후보 } Console.Write(sb); }}
C++main.cpp · 52 줄
#include <algorithm>#include <iostream>#include <map>#include <sstream>#include <string>#include <vector>int main() { int c, v; std::cin >> c >> v; std::vector<std::string> remaining(c); // 남은 후보, 처음 적힌 차례대로 for (auto& name : remaining) std::cin >> name; std::string line; std::getline(std::cin, line); // 후보 줄의 끝 std::vector<std::vector<std::string>> ballots(v); for (auto& ballot : ballots) { std::getline(std::cin, line); std::istringstream in(line); for (std::string name; in >> name;) ballot.push_back(name); } auto is_left = [&](const std::string& name) { return std::find(remaining.begin(), remaining.end(), name) != remaining.end(); }; while (true) { std::map<std::string, int> votes; for (const auto& name : remaining) votes[name] = 0; // 0표인 후보도 먼저 넣어 둔다 int active = 0; // 남은 후보를 하나라도 적은 투표지 수 for (const auto& ballot : ballots) { auto first = std::find_if(ballot.begin(), ballot.end(), is_left); // 가장 앞에 적힌 남은 후보 if (first != ballot.end()) { votes[*first]++; active++; } } for (size_t i = 0; i < remaining.size(); i++) std::cout << (i ? " " : "") << remaining[i] << ":" << votes[remaining[i]]; std::cout << "\n"; int best = -1, fewest = v + 1; std::string leader, loser; for (const auto& name : remaining) { if (votes[name] > best) { best = votes[name]; leader = name; } if (votes[name] <= fewest) { fewest = votes[name]; loser = name; } // <=: 동점이면 뒤에 적힌 후보 } if (2 * best > active || remaining.size() == 1) { std::cout << leader << "\n"; break; } remaining.erase(std::find(remaining.begin(), remaining.end(), loser)); }}
Cmain.c · 63 줄
#include <stdio.h>#include <string.h>#define MAXC 20#define MAXV 1000static char cand[MAXC][11]; /* 후보 이름, 처음 적힌 차례 */static int left[MAXC]; /* 1이면 아직 남은 후보 */static int ballot[MAXV][MAXC]; /* 투표지마다 후보 번호 */static int len[MAXV];static int cand_id(const char *name, int c) { for (int i = 0; i < c; i++) if (strcmp(cand[i], name) == 0) return i; return -1;}int main(void) { int c, v; scanf("%d %d", &c, &v); for (int i = 0; i < c; i++) { scanf("%10s", cand[i]); left[i] = 1; } getchar(); /* 후보 줄의 끝 */ char line[256]; for (int b = 0; b < v; b++) { fgets(line, sizeof line, stdin); len[b] = 0; for (char *tok = strtok(line, " \r\n"); tok; tok = strtok(NULL, " \r\n")) ballot[b][len[b]++] = cand_id(tok, c); } int count_left = c; while (1) { int votes[MAXC] = {0}; /* 후보 번호마다 표 수 */ int active = 0; /* 남은 후보를 하나라도 적은 투표지 수 */ for (int b = 0; b < v; b++) { for (int k = 0; k < len[b]; k++) { if (left[ballot[b][k]]) { /* 가장 앞에 적힌 남은 후보 */ votes[ballot[b][k]]++; active++; break; } } } int best = -1, fewest = v + 1, leader = -1, loser = -1, printed = 0; for (int i = 0; i < c; i++) { if (!left[i]) continue; printf("%s%s:%d", printed++ ? " " : "", cand[i], votes[i]); if (votes[i] > best) { best = votes[i]; leader = i; } if (votes[i] <= fewest) { fewest = votes[i]; loser = i; } /* <=: 동점이면 뒤에 적힌 후보 */ } putchar('\n'); if (2 * best > active || count_left == 1) { printf("%s\n", cand[leader]); break; } left[loser] = 0; count_left--; } return 0;}
Craykonmain.cray · 62 줄
first = 콘솔.줄읽기().공백제거().나누기();v = first[1].수로변환();remaining = 콘솔.줄읽기().공백제거().나누기(); // 남은 후보, 처음 적힌 차례대로ballots = [];반복 (i = 0; i < v; i++){ ballots.넣기(콘솔.줄읽기().공백제거().나누기());}끝남 = 거짓;동안 (!끝남){ votes = 사전(); 각각 (name 에서 remaining) { votes[name] = 0; // 0표인 후보도 먼저 넣어 둔다 } active = 0; // 남은 후보를 하나라도 적은 투표지 수 각각 (ballot 에서 ballots) { 각각 (name 에서 ballot) { 만약 (remaining.있나(name)) { votes[name] = votes[name] + 1; active++; 그만; } } } parts = []; best = -1; fewest = v + 1; leader = ""; loser = ""; 각각 (name 에서 remaining) { parts.넣기(name + ":" + votes[name]); 만약 (votes[name] > best) { best = votes[name]; leader = name; } 만약 (votes[name] <= fewest) { fewest = votes[name]; loser = name; } } 콘솔.쓰기(parts.잇기(" ")); 만약 (2 * best > active || remaining.개수 == 1) { 콘솔.쓰기(leader); 끝남 = 참; } 아니면 { remaining.빼기(loser); }}