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); }}