창고에 꾸러미 n개가 차례로 들어온다. 꾸러미는 들어온 차례대로 1번부터 번호를 붙인다.
꾸러미마다 이름표 하나와, 안에 든 물건 번호 k개가 차례대로 적혀 있다.
두 꾸러미가 "똑같다"는 것은 이름표가 같고, 물건 번호의 수가 같고, 자리마다 물건 번호가 같다는 뜻이다.
두 꾸러미가 "구성이 같다"는 것은 이름표가 같고, 물건 번호를 차례와 상관없이 보았을 때 같은 번호가 같은 개수만큼 들어 있다는 뜻이다. 다시 말해 양쪽의 물건 번호를 작은 것부터 늘어놓으면 똑같아진다.
똑같은 두 꾸러미는 구성도 같다. 물건이 하나도 없는 꾸러미끼리는 이름표가 같으면 똑같다.
첫 줄에 n, 다음 n줄에 1번부터 차례로 꾸러미가 "이름표 k 번호1 … 번호k"로 주어진다.
꾸러미마다 한 줄에 두 수 a와 b를 빈칸 하나로 띄워 출력하라.
a는 그 꾸러미와 똑같은 꾸러미 가운데 가장 먼저 들어온 것의 번호이고, b는 구성이 같은 꾸러미 가운데 가장 먼저 들어온 것의 번호다. 그 꾸러미 자신도 셈에 넣는다.
마지막 줄에는 두 수를 빈칸 하나로 띄워 출력하라.
첫째 수는 똑같은 꾸러미끼리를 한 가지로 셀 때 꾸러미가 모두 몇 가지인지이고, 둘째 수는 구성이 같은 꾸러미끼리를 한 가지로 셀 때 모두 몇 가지인지다.
입력
1 ≤ n ≤ 5,000, 0 ≤ k ≤ 10, 0 ≤ 물건 번호 ≤ 10⁹. 이름표는 영어 소문자 1~10자다.
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
핵심은 '값이 같은 목록'을 사전의 열쇠로 쓰는 일인데, 목록끼리의 ==와 열쇠 비교가 언어마다 달라요. Python은 [1, 2] == [1, 2]가 참이지만 바뀔 수 있는 list는 열쇠가 못 되니 (label, tuple(codes))처럼 튜플로 만들어요. C++는 std::vector·std::string의 ==·<가 값으로 비교해서 std::map<std::pair<std::string, std::vector<int>>, int>를 그대로 써요. Java List.equals는 원소마다 equals로 비교하니 record Key(String label, List<Integer> codes)가 열쇠로 돼요(record가 equals·hashCode를 만들어 줘요). JavaScript·TypeScript의 Map·===, C#의 List<int>, 크레이콘의 목록 ==는 같은 목록(참조)인지만 물어서, 값이 같아지는 문자열 열쇠 label + " " + codes.join(",")(크레이콘 codes.잇기(","))를 만들어요. C는 사전이 없으니 qsort로 같은 것끼리 모은 뒤 이웃끼리 비교하고, 이름표는 strcmp로 비교해요. 구성 열쇠는 정렬한 복사본으로 만들어요. Python sorted()·C# OrderBy·Java new ArrayList<>(codes)·JS [...codes]·C++ std::vector<int> sorted = codes;·크레이콘 codes.부분목록(0, codes.개수)가 복사본이에요. 함정 일곱: ① JS에서 [label, codes] 배열을 Map 열쇠로 쓰면 줄마다 새 배열이라 모든 꾸러미가 서로 달라요. ② C#의 (string, List<int>) 튜플 열쇠도 튜플은 값으로 비교하지만 그 안의 List<int>는 참조로 비교해서 같은 결과예요. ③ Java record Key(String label, int[] codes)는 컴파일되지만 배열 멤버는 같은 배열인지만 비교해요(Arrays.equals가 아니에요). ④ 사이에 나눔표 없이 label + "".join(...)로 이어 붙이면 [1, 23]과 [12, 3]이 둘 다 123이 돼서 다른 꾸러미가 같아져요. ⑤ JS codes.sort()는 복사본이 아니라 codes 자체를 정렬하고 같은 배열을 돌려줘서, 똑같음 열쇠까지 정렬된 번호로 만들어져요. ⑥ 크레이콘 sorted = codes;도 같은 목록에 이름만 하나 더 붙어서 같은 일이 생겨요. ⑦ C에서 a->label == b->label·<는 두 배열의 주소를 비교해서 이름표가 같아도 늘 달라요.
Pythonmain.py · 18 줄
import syslines = sys.stdin.read().split("\n")n = int(lines[0])first_same = {} # (이름표, 번호 튜플) → 가장 먼저 들어온 번호first_bag = {} # (이름표, 정렬한 번호 튜플) → 가장 먼저 들어온 번호out = []for i in range(1, n + 1): label, k, *rest = lines[i].split() codes = [int(x) for x in rest] # 목록(list)은 바뀔 수 있어서 열쇠가 못 된다. 튜플은 값으로 같고 해시도 값으로 정해진다 same = (label, tuple(codes)) bag = (label, tuple(sorted(codes))) # sorted는 새 목록을 만든다: codes는 그대로 a = first_same.setdefault(same, i) b = first_bag.setdefault(bag, i) out.append(f"{a} {b}")out.append(f"{len(first_same)} {len(first_bag)}")print("\n".join(out))
JavaScriptmain.js · 20 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);// Map은 열쇠를 SameValueZero로 비교한다: 배열은 같은 배열(참조)일 때만 같다.// 그래서 값이 같으면 같아지는 문자열 열쇠로 바꾼다. 사이에 쉼표·빈칸을 넣어 경계를 지킨다const firstSame = new Map();const firstBag = new Map();const out = [];for (let i = 1; i <= n; i++) { const [label, , ...rest] = lines[i].trim().split(" "); const codes = rest.map(Number); const sameKey = `${label} ${codes.join(",")}`; // sort는 제자리에서 바꾸고 같은 배열을 돌려준다: 복사본([...codes])을 정렬한다. // 비교 함수가 없으면 문자열로 정렬하니 (a, b) => a - b를 준다 const bagKey = `${label} ${[...codes].sort((a, b) => a - b).join(",")}`; if (!firstSame.has(sameKey)) firstSame.set(sameKey, i); if (!firstBag.has(bagKey)) firstBag.set(bagKey, i); out.push(`${firstSame.get(sameKey)} ${firstBag.get(bagKey)}`);}out.push(`${firstSame.size} ${firstBag.size}`);console.log(out.join("\n"));
TypeScriptmain.ts · 25 줄
import { readFileSync } from "node:fs";const lines = readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);// 배열은 ===로도 Map 열쇠로도 같은 배열(참조)일 때만 같다: 값으로 같아지는 문자열 열쇠를 만든다function keyOf(label: string, codes: readonly number[]): string { return `${label} ${codes.join(",")}`; // 사이에 빈칸·쉼표를 넣어 [1, 23]과 [12, 3]을 가른다}const firstSame = new Map<string, number>();const firstBag = new Map<string, number>();const out: string[] = [];for (let i = 1; i <= n; i++) { const [label, , ...rest] = lines[i].trim().split(" "); const codes: readonly number[] = rest.map(Number); const sorted = [...codes].sort((a, b) => a - b); // 복사본을 정렬한다(readonly라 codes.sort는 타입 오류) const sameKey = keyOf(label, codes); const bagKey = keyOf(label, sorted); if (!firstSame.has(sameKey)) firstSame.set(sameKey, i); if (!firstBag.has(bagKey)) firstBag.set(bagKey, i); out.push(`${firstSame.get(sameKey)} ${firstBag.get(bagKey)}`);}out.push(`${firstSame.size} ${firstBag.size}`);console.log(out.join("\n"));
JavaMain.java · 36 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class Main { // record는 equals·hashCode를 멤버마다 equals로 만들어 준다. // List.equals는 길이와 자리마다의 값을 비교한다(배열 int[]라면 같은 배열인지만 본다) record Key(String label, List<Integer> codes) {} public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); Map<Key, Integer> firstSame = new HashMap<>(); Map<Key, Integer> firstBag = new HashMap<>(); StringBuilder out = new StringBuilder(); for (int i = 1; i <= n; i++) { String[] p = br.readLine().trim().split(" "); List<Integer> codes = new ArrayList<>(); for (int j = 2; j < p.length; j++) codes.add(Integer.parseInt(p[j])); List<Integer> sorted = new ArrayList<>(codes); // 복사본을 정렬한다 sorted.sort(null); // putIfAbsent: 열쇠가 없으면 i를 넣고 null을, 있으면 먼저 넣은 값을 돌려준다 Integer a = firstSame.putIfAbsent(new Key(p[0], codes), i); Integer b = firstBag.putIfAbsent(new Key(p[0], sorted), i); if (a == null) a = i; if (b == null) b = i; out.append(a).append(' ').append(b).append('\n'); } out.append(firstSame.size()).append(' ').append(firstBag.size()).append('\n'); System.out.print(out); }}
C#Main.cs · 32 줄
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { var input = Console.In; int n = int.Parse(input.ReadLine()!.Trim()); // List<int>는 Equals가 참조 비교라 열쇠로 쓰면 값이 같아도 다른 열쇠가 된다. // 값으로 같아지는 문자열 열쇠를 만든다(사이에 빈칸·쉼표를 넣어 경계를 지킨다) var firstSame = new Dictionary<string, int>(); var firstBag = new Dictionary<string, int>(); var sb = new StringBuilder(); for (int i = 1; i <= n; i++) { string[] p = input.ReadLine()!.Trim().Split(' '); string label = p[0]; int[] codes = p.Skip(2).Select(int.Parse).ToArray(); int[] sorted = codes.OrderBy(x => x).ToArray(); // 새 배열: codes는 그대로 string sameKey = label + " " + string.Join(",", codes); string bagKey = label + " " + string.Join(",", sorted); if (!firstSame.TryGetValue(sameKey, out int a)) firstSame[sameKey] = a = i; if (!firstBag.TryGetValue(bagKey, out int b)) firstBag[bagKey] = b = i; sb.Append(a).Append(' ').Append(b).Append('\n'); } sb.Append(firstSame.Count).Append(' ').Append(firstBag.Count).Append('\n'); Console.Write(sb); }}
C++main.cpp · 33 줄
#include <algorithm>#include <iostream>#include <map>#include <string>#include <utility>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; // std::string과 std::vector는 ==와 <가 값(길이와 자리마다의 원소)으로 비교한다. // 그래서 pair<string, vector<int>>를 그대로 map의 열쇠로 쓸 수 있다 using Key = std::pair<std::string, std::vector<int>>; std::map<Key, int> firstSame, firstBag; std::string out; for (int i = 1; i <= n; i++) { std::string label; int k; std::cin >> label >> k; std::vector<int> codes(k); for (int &x : codes) std::cin >> x; std::vector<int> sorted = codes; // vector 대입은 복사: codes는 그대로 std::sort(sorted.begin(), sorted.end()); // emplace는 열쇠가 이미 있으면 넣지 않고, 있던 칸을 가리키는 반복자를 돌려준다 int a = firstSame.emplace(Key{label, codes}, i).first->second; int b = firstBag.emplace(Key{label, sorted}, i).first->second; out += std::to_string(a) + ' ' + std::to_string(b) + '\n'; } out += std::to_string(firstSame.size()) + ' ' + std::to_string(firstBag.size()) + '\n'; std::cout << out;}
Cmain.c · 73 줄
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 5000typedef struct { char label[11]; int k; int codes[10]; /* 들어온 차례 그대로 */ int sorted[10]; /* 작은 것부터 늘어놓은 것 */} Parcel;static Parcel p[MAXN];static int order[MAXN];static int cmp_int(const void *a, const void *b) { int x = *(const int *)a, y = *(const int *)b; return (x > y) - (x < y);}/* 두 꾸러미를 비교한다. 문자열은 ==로 비교하면 주소를 비교하니 strcmp로, 배열은 길이를 먼저 보고 칸마다 비교한다 */static int compare(const Parcel *a, const Parcel *b, int use_sorted) { int c = strcmp(a->label, b->label); if (c != 0) return c; if (a->k != b->k) return a->k - b->k; const int *x = use_sorted ? a->sorted : a->codes; const int *y = use_sorted ? b->sorted : b->codes; for (int j = 0; j < a->k; j++) if (x[j] != y[j]) return x[j] < y[j] ? -1 : 1; return 0;}static int use_sorted_now;static int cmp_order(const void *a, const void *b) { int i = *(const int *)a, j = *(const int *)b; int c = compare(&p[i], &p[j], use_sorted_now); return c != 0 ? c : i - j; /* 같은 것끼리는 먼저 들어온 것이 앞에 */}/* 같은 것끼리 모이도록 번호를 정렬하고, 무리마다 맨 앞(가장 먼저 들어온 것)의 번호를 적는다 */static int group(int n, int use_sorted, int *first) { for (int i = 0; i < n; i++) order[i] = i; use_sorted_now = use_sorted; qsort(order, (size_t)n, sizeof order[0], cmp_order); int kinds = 0, head = 0; for (int t = 0; t < n; t++) { if (t == 0 || compare(&p[order[t]], &p[order[t - 1]], use_sorted) != 0) { head = order[t]; kinds++; } first[order[t]] = head; } return kinds;}int main(void) { static int first_same[MAXN], first_bag[MAXN]; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%10s %d", p[i].label, &p[i].k); for (int j = 0; j < p[i].k; j++) scanf("%d", &p[i].codes[j]); memcpy(p[i].sorted, p[i].codes, sizeof p[i].codes); qsort(p[i].sorted, (size_t)p[i].k, sizeof(int), cmp_int); } int same_kinds = group(n, 0, first_same); int bag_kinds = group(n, 1, first_bag); for (int i = 0; i < n; i++) printf("%d %d\n", first_same[i] + 1, first_bag[i] + 1); printf("%d %d\n", same_kinds, bag_kinds); return 0;}
Craykonmain.cray · 33 줄
n = 콘솔.줄읽기().수로변환();// 목록끼리 ==는 같은 목록인지만 묻고, 사전의 열쇠는 문자열이나 수만 된다.// 그래서 값이 같으면 같아지는 문자열 열쇠를 만든다(사이에 빈칸·쉼표를 넣는다)firstSame = 사전();firstBag = 사전();kinds = 0;bagKinds = 0;반복 (i = 1; i <= n; i++){ p = 콘솔.줄읽기().공백제거().나누기(" "); label = p[0]; codes = []; 반복 (j = 2; j < p.개수; j++) { codes.넣기(p[j].수로변환()); } sorted = codes.부분목록(0, codes.개수); // 새 목록: 정렬해도 codes는 그대로 sorted.정렬(); sameKey = label + " " + codes.잇기(","); bagKey = label + " " + sorted.잇기(","); 만약 (!firstSame.있나(sameKey)) { firstSame[sameKey] = i; kinds = kinds + 1; } 만약 (!firstBag.있나(bagKey)) { firstBag[bagKey] = i; bagKinds = bagKinds + 1; } 콘솔.쓰기(firstSame[sameKey] + " " + firstBag[bagKey]);}콘솔.쓰기(kinds + " " + bagKinds);