import sysfrom fractions import Fractionfrom math import gcd, lcmlines = sys.stdin.read().split("\n")n = int(lines[0])groups = {} # 비율 열쇠(재료 이름 차례로 늘어놓은 (이름, 정수) 튜플) → 요리 이름들. dict는 넣은 차례를 지킨다for i in range(1, n + 1): parts = lines[i].split() name, c = parts[0], int(parts[1]) amount = {} # 재료 → 양(분수). 같은 재료가 또 나오면 더한다 for j in range(c): ing, q = parts[2 + 2 * j], parts[3 + 2 * j] amount[ing] = amount.get(ing, Fraction(0)) + Fraction(q) # Fraction("3/4")도, Fraction("2")도 된다 # 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 den = lcm(*(a.denominator for a in amount.values())) whole = {ing: int(a * den) for ing, a in amount.items()} g = gcd(*whole.values()) key = tuple(sorted((ing, v // g) for ing, v in whole.items())) # 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 groups.setdefault(key, []).append(name)out = [str(len(groups))]for key, names in groups.items(): out.append(" ".join(f"{ing}:{v}" for ing, v in key) + " = " + " ".join(names))print("\n".join(out))
JavaScriptmain.js · 37 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));const n = Number(lines[0]);const groups = new Map(); // 비율 열쇠(문자열) → 요리 이름들. Map은 넣은 차례를 지킨다for (let i = 1; i <= n; i++) { const parts = lines[i].trim().split(" "); const name = parts[0]; const c = Number(parts[1]); const amount = new Map(); // 재료 → [분자, 분모](약분해 둔다). 같은 재료가 또 나오면 더한다 for (let j = 0; j < c; j++) { const ing = parts[2 + 2 * j]; const [p, q = "1"] = parts[3 + 2 * j].split("/"); // "3/4" → 3, 4 / "2" → 2, 1 const [a, b] = amount.get(ing) ?? [0, 1]; let num = a * Number(q) + Number(p) * b; let den = b * Number(q); const g = gcd(num, den); amount.set(ing, [num / g, den / g]); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 let lcm = 1; for (const [, den] of amount.values()) lcm = (lcm / gcd(lcm, den)) * den; const ings = [...amount.keys()].sort(); // 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 const whole = ings.map((ing) => { const [num, den] = amount.get(ing); return num * (lcm / den); }); const g = whole.reduce(gcd); const key = ings.map((ing, k) => `${ing}:${whole[k] / g}`).join(" "); // 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 if (!groups.has(key)) groups.set(key, []); groups.get(key).push(name);}const out = [String(groups.size)];for (const [key, names] of groups) out.push(`${key} = ${names.join(" ")}`);console.log(out.join("\n"));
TypeScriptmain.ts · 42 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));type Frac = [num: number, den: number];const n = Number(lines[0]);const groups = new Map<string, string[]>(); // 비율 열쇠(문자열) → 요리 이름들. Map은 넣은 차례를 지킨다for (let i = 1; i <= n; i++) { const parts = lines[i].trim().split(" "); const name = parts[0]; const c = Number(parts[1]); const amount = new Map<string, Frac>(); // 재료 → [분자, 분모](약분해 둔다). 같은 재료가 또 나오면 더한다 for (let j = 0; j < c; j++) { const ing = parts[2 + 2 * j]; const [p, q = "1"] = parts[3 + 2 * j].split("/"); // "3/4" → 3, 4 / "2" → 2, 1 const [a, b] = amount.get(ing) ?? [0, 1]; const num = a * Number(q) + Number(p) * b; const den = b * Number(q); const g = gcd(num, den); amount.set(ing, [num / g, den / g]); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 let lcm = 1; for (const [, den] of amount.values()) lcm = (lcm / gcd(lcm, den)) * den; const ings: string[] = [...amount.keys()].sort(); // 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 const whole: number[] = ings.map((ing) => { const [num, den] = amount.get(ing)!; return num * (lcm / den); }); const g = whole.reduce(gcd); const key = ings.map((ing, k) => `${ing}:${whole[k] / g}`).join(" "); // 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 const names = groups.get(key); if (names) names.push(name); else groups.set(key, [name]);}const out: string[] = [String(groups.size)];for (const [key, names] of groups) out.push(`${key} = ${names.join(" ")}`);console.log(out.join("\n"));
JavaMain.java · 45 行
import java.io.*;import java.util.*;public class Main { static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); // 비율 열쇠 → 요리 이름들. LinkedHashMap은 넣은 차례를 지킨다(HashMap은 차례가 제멋대로) Map<List<String>, List<String>> groups = new LinkedHashMap<>(); for (int i = 0; i < n; i++) { String[] parts = br.readLine().trim().split(" "); String name = parts[0]; int c = Integer.parseInt(parts[1]); // 재료 → {분자, 분모}(약분해 둔다). TreeMap이라 이름 차례로 늘어선다 TreeMap<String, int[]> amount = new TreeMap<>(); for (int j = 0; j < c; j++) { String ing = parts[2 + 2 * j]; String[] pq = parts[3 + 2 * j].split("/"); int p = Integer.parseInt(pq[0]); int q = pq.length > 1 ? Integer.parseInt(pq[1]) : 1; int[] f = amount.getOrDefault(ing, new int[] {0, 1}); int num = f[0] * q + p * f[1], den = f[1] * q; // 같은 재료가 또 나오면 더한다 int g = gcd(num, den); amount.put(ing, new int[] {num / g, den / g}); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 int lcm = 1; for (int[] f : amount.values()) lcm = lcm / gcd(lcm, f[1]) * f[1]; int g = 0; for (int[] f : amount.values()) g = gcd(g, f[0] * (lcm / f[1])); // 열쇠는 List<String>: List는 내용으로 equals·hashCode를 만든다(배열 String[]은 같은 객체일 때만 같다) List<String> key = new ArrayList<>(); for (Map.Entry<String, int[]> e : amount.entrySet()) key.add(e.getKey() + ":" + e.getValue()[0] * (lcm / e.getValue()[1]) / g); groups.computeIfAbsent(key, k -> new ArrayList<>()).add(name); } StringBuilder sb = new StringBuilder(); sb.append(groups.size()).append('\n'); for (Map.Entry<List<String>, List<String>> e : groups.entrySet()) sb.append(String.join(" ", e.getKey())).append(" = ").append(String.join(" ", e.getValue())).append('\n'); System.out.print(sb); }}
C#Main.cs · 52 行
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b); static void Main() { int n = int.Parse(Console.ReadLine()!.Trim()); // 비율 열쇠(문자열) → 요리 이름들. 넣은 차례를 따로 적어 둔다(Dictionary의 열거 차례는 약속되어 있지 않다) var groups = new Dictionary<string, List<string>>(); var order = new List<string>(); for (int i = 0; i < n; i++) { var parts = Console.ReadLine()!.Trim().Split(' '); string name = parts[0]; int c = int.Parse(parts[1]); // 재료 → (분자, 분모)(약분해 둔다). 같은 재료가 또 나오면 더한다 var amount = new SortedDictionary<string, (int Num, int Den)>(StringComparer.Ordinal); for (int j = 0; j < c; j++) { string ing = parts[2 + 2 * j]; var pq = parts[3 + 2 * j].Split('/'); int p = int.Parse(pq[0]); int q = pq.Length > 1 ? int.Parse(pq[1]) : 1; var (a, b) = amount.TryGetValue(ing, out var f) ? f : (0, 1); int num = a * q + p * b, den = b * q; int g = Gcd(num, den); amount[ing] = (num / g, den / g); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 int lcm = amount.Values.Aggregate(1, (l, f) => l / Gcd(l, f.Den) * f.Den); int gAll = amount.Values.Aggregate(0, (g, f) => Gcd(g, f.Num * (lcm / f.Den))); // SortedDictionary라 이름 차례로 늘어선다. 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 string key = string.Join(" ", amount.Select(e => $"{e.Key}:{e.Value.Num * (lcm / e.Value.Den) / gAll}")); if (!groups.TryGetValue(key, out var names)) { names = new List<string>(); groups[key] = names; order.Add(key); } names.Add(name); } var sb = new StringBuilder(); sb.Append(groups.Count).Append('\n'); foreach (var key in order) sb.Append(key).Append(" = ").Append(string.Join(" ", groups[key])).Append('\n'); Console.Write(sb); }}
C++main.cpp · 56 行
#include <iostream>#include <map>#include <numeric>#include <string>#include <utility>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; // 비율 열쇠 → 묶음 번호. 열쇠는 (재료, 정수) 쌍의 vector: std::map은 vector도 내용으로 견준다 std::map<std::vector<std::pair<std::string, int>>, int> index; std::vector<std::vector<std::pair<std::string, int>>> keys; // 묶음마다 열쇠(나온 차례대로) std::vector<std::vector<std::string>> names; for (int i = 0; i < n; i++) { std::string name; int c; std::cin >> name >> c; std::map<std::string, std::pair<int, int>> amount; // 재료 → (분자, 분모). std::map이라 이름 차례로 늘어선다 for (int j = 0; j < c; j++) { std::string ing, qs; std::cin >> ing >> qs; // std::stoi("3/4")는 '/' 앞에서 멈춰 3을 준다: 나눗셈 기호를 직접 찾아 자른다 auto slash = qs.find('/'); int p = std::stoi(qs.substr(0, slash)); int q = slash == std::string::npos ? 1 : std::stoi(qs.substr(slash + 1)); auto [it, fresh] = amount.try_emplace(ing, 0, 1); // 같은 재료가 또 나오면 더한다 auto &[num, den] = it->second; int nn = num * q + p * den, dd = den * q; int g = std::gcd(nn, dd); num = nn / g, den = dd / g; } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 int l = 1, g = 0; for (const auto &[ing, f] : amount) l = std::lcm(l, f.second); for (const auto &[ing, f] : amount) g = std::gcd(g, f.first * (l / f.second)); std::vector<std::pair<std::string, int>> key; for (const auto &[ing, f] : amount) key.emplace_back(ing, f.first * (l / f.second) / g); auto [it, fresh] = index.try_emplace(key, static_cast<int>(keys.size())); if (fresh) { keys.push_back(key); names.emplace_back(); } names[it->second].push_back(name); } std::cout << keys.size() << '\n'; for (size_t k = 0; k < keys.size(); k++) { for (size_t t = 0; t < keys[k].size(); t++) std::cout << (t ? " " : "") << keys[k][t].first << ':' << keys[k][t].second; std::cout << " ="; for (const auto &nm : names[k]) std::cout << ' ' << nm; std::cout << '\n'; }}
Cmain.c · 67 行
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 2000#define MAXC 10#define KEYLEN 256 /* 재료 10개 × ("이름 10글자" + ":" + 수 8자리 + 빈칸) */typedef struct { char ing[11]; int num, den; /* 지금까지 더한 양(약분해 둔다) */} Item;static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }static int by_name(const void *x, const void *y) { return strcmp(((const Item *)x)->ing, ((const Item *)y)->ing); }static char keys[MAXN][KEYLEN]; /* 묶음마다 비율 열쇠(나온 차례대로) */static char names[MAXN][11]; /* 요리 이름 */static int group_of[MAXN]; /* 요리 → 묶음 번호 */int main(void) { int n, groups = 0; if (scanf("%d", &n) != 1) return 0; for (int i = 0; i < n; i++) { int c, k = 0; Item item[MAXC]; scanf("%10s %d", names[i], &c); for (int j = 0; j < c; j++) { char ing[11], qs[16]; int p, q = 1; scanf("%10s %15s", ing, qs); if (sscanf(qs, "%d/%d", &p, &q) < 2) q = 1; /* "2"는 2/1 */ int t = 0; while (t < k && strcmp(item[t].ing, ing) != 0) t++; /* 같은 재료가 또 나오면 더한다 */ if (t == k) { strcpy(item[k].ing, ing); item[k].num = 0, item[k].den = 1; k++; } int num = item[t].num * q + p * item[t].den, den = item[t].den * q; int g = gcd(num, den); item[t].num = num / g, item[t].den = den / g; } qsort(item, k, sizeof(Item), by_name); /* 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 */ /* 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 */ int lcm = 1, g = 0; for (int t = 0; t < k; t++) lcm = lcm / gcd(lcm, item[t].den) * item[t].den; for (int t = 0; t < k; t++) g = gcd(g, item[t].num * (lcm / item[t].den)); char key[KEYLEN]; int len = 0; for (int t = 0; t < k; t++) /* 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 */ len += snprintf(key + len, KEYLEN - len, "%s%s:%d", t ? " " : "", item[t].ing, item[t].num * (lcm / item[t].den) / g); int found = 0; while (found < groups && strcmp(keys[found], key) != 0) found++; /* 요리 2,000개라 앞에서부터 찾아도 빠르다 */ if (found == groups) strcpy(keys[groups++], key); group_of[i] = found; } printf("%d\n", groups); for (int g = 0; g < groups; g++) { printf("%s =", keys[g]); for (int i = 0; i < n; i++) if (group_of[i] == g) printf(" %s", names[i]); printf("\n"); } return 0;}
Craykonmain.cray · 72 行
최대공약수(a, b){ 当 (b != 0) { t = a % b; a = b; b = t; } 返回 a;}n = 控制台.读行().去空白().转数字();groups = 字典(); // 비율 열쇠(문자열) → 요리 이름들. 사전의 열쇠목록은 넣은 차례를 지킨다循环 (i = 0; i < n; i++){ parts = 控制台.读行().去空白().分割(" "); name = parts[0]; c = parts[1].转数字(); num = 字典(); // 재료 → 지금까지 더한 양의 분자(약분해 둔다). 같은 재료가 또 나오면 더한다 den = 字典(); // 재료 → 분모 循环 (j = 0; j < c; j++) { ing = parts[2 + 2 * j]; pq = parts[3 + 2 * j].分割("/"); // "3/4" → ["3", "4"], "2" → ["2"] p = pq[0].转数字(); q = 1; 如果 (pq.数量 > 1) { q = pq[1].转数字(); } 如果 (!num.包含(ing)) { num[ing] = 0; den[ing] = 1; } a = num[ing] * q + p * den[ing]; b = den[ing] * q; g = 최대공약수(a, b); num[ing] = a / g; den[ing] = b / g; } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 ings = num.键列表; ings.排序(); // 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 lcm = 1; 遍历 (x 在 ings) { lcm = lcm / 최대공약수(lcm, den[x]) * den[x]; } g = 0; 遍历 (x 在 ings) { g = 최대공약수(g, num[x] * (lcm / den[x])); } 조각 = []; 遍历 (x 在 ings) { 조각.添加(x + ":" + num[x] * (lcm / den[x]) / g); // 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 } key = 조각.连接(" "); 如果 (!groups.包含(key)) { groups[key] = []; } groups[key].添加(name);}控制台.输出(groups.数量);遍历 (key 在 groups.键列表){ 控制台.输出(key + " = " + groups[key].连接(" "));}