짝 활동을 하려고 학생들이 같이 하고 싶은 친구를 한 명씩 적어 냈다.
첫 줄에 신청 수 n이, 다음 n줄에 들어온 차례대로 신청 "a b"가 주어진다. a가 b를 골랐다는 뜻이다.
같은 학생이 여러 번 신청하면 마지막 신청만 남는다.
학생의 차례는 그 학생이 처음 신청한 차례이고, 다시 신청해도 바뀌지 않는다.
두 학생 x, y가 남은 신청에서 서로를 골랐으면 서로 짝이다.
학생은 자기 자신을 고르지 않는다. 고른 친구가 한 번도 신청하지 않았을 수도 있다.
첫 줄에 서로 짝인 쌍의 수를 출력하라.
이어서 쌍마다 한 줄에 "x y"를 출력한다. x는 두 학생 가운데 차례가 앞선 학생이다.
쌍은 x의 차례대로 출력한다. 쌍이 없으면 첫 줄의 0만 출력한다.
입력
1 ≤ n ≤ 5,000. 이름은 영어 소문자 1~10글자이고, 한 신청의 두 이름은 다르다
출력
첫 줄에 쌍의 수, 이어서 쌍마다 한 줄(x y), x의 차례대로
예시 1 · stdin
7
mina jun
jun sora
sora jun
dan mina
mina dan
eve kai
jun mina
stdout
1
mina dan
예시 2 · stdin
3
b a
a b
c a
stdout
1
b a
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
마지막 신청을 사전에 넣고(pick[a] = b), 그 사전을 처음 넣은 차례대로 돌며 pick[b] == a인지 보면 돼요. 열쇠가 이미 있을 때 값을 바꿔 넣어도 그 열쇠의 차례는 처음 넣은 자리 그대로예요(Python dict, JS·TS Map, Java LinkedHashMap, 크레이콘 사전의 열쇠목록). 처음 신청만 남기는 setdefault·putIfAbsent·TryAdd는 틀려요. 차례가 함정이에요. Java HashMap과 C++ unordered_map은 차례가 뒤섞이고, C++ std::map은 이름의 사전 순으로 돌아요. C# Dictionary의 도는 차례는 문서가 약속하지 않으니, 처음 신청한 이름을 목록에 따로 적어 그 목록을 돌아요. 고른 친구가 신청하지 않았을 수 있다는 것도 함정이에요. C# pick[b]는 KeyNotFoundException을 던지니 TryGetValue로, Python은 pick.get(b)로, 크레이콘은 있나로 먼저 물어요(없는 열쇠를 읽으면 멈춰요). C++ pick[b]는 오류 없이 빈 값을 새로 넣어 버리니 find를 써요. 사전을 돌며 서로 고른 것만 보면 같은 쌍이 x 차례와 y 차례에 두 번 나오니, 이미 쓴 짝을 표시해 둬요. C에는 사전이 없어서 처음 신청한 차례대로 배열에 적고 strcmp로 앞에서부터 찾아요.
Pythonmain.py · 16 줄
n = int(input())pick = {}for _ in range(n): a, b = input().split() pick[a] = b # 다시 내면 값만 바뀌고, 열쇠의 차례(처음 넣은 차례)는 그대로다pairs = []done = set()for a, b in pick.items(): # dict는 열쇠를 처음 넣은 차례대로 돈다 if a in done: continue if pick.get(b) == a: pairs.append(f"{a} {b}") done.add(b) # b 차례가 와도 같은 쌍을 다시 쓰지 않는다print(len(pairs))for p in pairs: print(p)
JavaScriptmain.js · 18 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);// Map은 열쇠를 처음 넣은 차례대로 돈다. set으로 값을 바꿔도 차례는 그대로다const pick = new Map();for (let i = 1; i <= n; i++) { const [a, b] = lines[i].trim().split(" "); pick.set(a, b);}const pairs = [];const done = new Set();for (const [a, b] of pick) { if (done.has(a)) continue; if (pick.get(b) === a) { pairs.push(`${a} ${b}`); done.add(b); }}console.log([String(pairs.length), ...pairs].join("\n"));
TypeScriptmain.ts · 19 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);// Map은 열쇠를 처음 넣은 차례대로 돈다. set으로 값을 바꿔도 차례는 그대로다const pick = new Map<string, string>();for (let i = 1; i <= n; i++) { const [a, b] = lines[i].trim().split(" "); pick.set(a, b);}const pairs: string[] = [];const done = new Set<string>();for (const [a, b] of pick) { if (done.has(a)) continue; if (pick.get(b) === a) { pairs.push(`${a} ${b}`); done.add(b); }}console.log([String(pairs.length), ...pairs].join("\n"));
JavaMain.java · 35 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashSet;import java.util.LinkedHashMap;import java.util.List;import java.util.Map;import java.util.Set;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); // HashMap은 차례가 뒤섞인다. LinkedHashMap은 처음 넣은 차례를 지키고, put으로 값을 바꿔도 차례는 그대로다 Map<String, String> pick = new LinkedHashMap<>(); for (int i = 0; i < n; i++) { String[] p = br.readLine().trim().split(" "); pick.put(p[0], p[1]); } List<String> pairs = new ArrayList<>(); Set<String> done = new HashSet<>(); for (Map.Entry<String, String> e : pick.entrySet()) { String a = e.getKey(), b = e.getValue(); if (done.contains(a)) continue; if (a.equals(pick.get(b))) { // b가 신청하지 않았으면 get은 null pairs.add(a + " " + b); done.add(b); } } StringBuilder out = new StringBuilder(); out.append(pairs.size()).append('\n'); for (String s : pairs) out.append(s).append('\n'); System.out.print(out); }}
C#Main.cs · 37 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); // Dictionary의 도는 차례는 문서가 약속하지 않으니, 처음 신청한 차례를 목록에 따로 적는다 var pick = new Dictionary<string, string>(); var order = new List<string>(); for (int i = 0; i < n; i++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); if (!pick.ContainsKey(p[0])) order.Add(p[0]); pick[p[0]] = p[1]; } var pairs = new List<string>(); var done = new HashSet<string>(); foreach (string a in order) { string b = pick[a]; if (done.Contains(a)) continue; // pick[b]는 b가 신청하지 않았으면 KeyNotFoundException — TryGetValue로 묻는다 if (pick.TryGetValue(b, out string back) && back == a) { pairs.Add(a + " " + b); done.Add(b); } } var sb = new StringBuilder(); sb.Append(pairs.Count).Append('\n'); foreach (string s in pairs) sb.Append(s).Append('\n'); Console.Write(sb); }}
C++main.cpp · 33 줄
#include <iostream>#include <string>#include <unordered_map>#include <unordered_set>#include <vector>int main() { std::ios::sync_with_stdio(false); int n; std::cin >> n; // std::map은 이름의 사전 순으로, unordered_map은 뒤섞인 차례로 돈다. 처음 신청한 차례는 따로 적는다 std::unordered_map<std::string, std::string> pick; std::vector<std::string> order; for (int i = 0; i < n; i++) { std::string a, b; std::cin >> a >> b; if (pick.find(a) == pick.end()) order.push_back(a); pick[a] = b; } std::vector<std::string> pairs; std::unordered_set<std::string> done; for (const std::string& a : order) { if (done.count(a)) continue; const std::string& b = pick[a]; auto it = pick.find(b); // pick[b]로 물으면 없는 b가 빈 값으로 생긴다 if (it != pick.end() && it->second == a) { pairs.push_back(a + " " + b); done.insert(b); } } std::cout << pairs.size() << "\n"; for (const std::string& s : pairs) std::cout << s << "\n";}
Cmain.c · 45 줄
#include <stdio.h>#include <string.h>/* C에는 사전이 없어서, 처음 신청한 차례대로 이름과 고른 친구를 배열에 적고 앞에서부터 찾는다 */#define MAXN 5000static char name[MAXN][11];static char pick[MAXN][11];static int done[MAXN];static int kinds = 0;static int find(const char *s) { for (int i = 0; i < kinds; i++) if (strcmp(name[i], s) == 0) return i; return -1;}int main(void) { int n; char a[16], b[16]; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%15s %15s", a, b); int k = find(a); if (k < 0) { k = kinds++; strcpy(name[k], a); } strcpy(pick[k], b); /* 다시 내면 고른 친구만 바뀐다 */ } int count = 0; static int first[MAXN], second[MAXN]; for (int i = 0; i < kinds; i++) { if (done[i]) continue; int j = find(pick[i]); if (j >= 0 && strcmp(pick[j], name[i]) == 0) { first[count] = i; second[count] = j; count++; done[j] = 1; } } printf("%d\n", count); for (int k = 0; k < count; k++) printf("%s %s\n", name[first[k]], name[second[k]]); return 0;}
Craykonmain.cray · 27 줄
n = 콘솔.줄읽기().수로변환();pick = 사전();반복 (i = 0; i < n; i++){ p = 콘솔.줄읽기().공백제거().나누기(" "); pick[p[0]] = p[1]; // 다시 내면 값만 바뀌고 열쇠의 차례는 그대로다}pairs = [];done = 사전();// 크레이콘 사전의 열쇠목록은 처음 넣은 차례다각각 (a 에서 pick.열쇠목록){ b = pick[a]; 만약 (!done.있나(a) && pick.있나(b)) { 만약 (pick[b] == a) { pairs.넣기(a + " " + b); done[b] = 참; } }}콘솔.쓰기(pairs.개수);각각 (s 에서 pairs){ 콘솔.쓰기(s);}