학교에서 짝을 적어 두는 장부 두 권을 쓴다.
사물함 장부(locker)는 사물함 번호(정수)와 학생 이름을 짝짓고, 별명 장부(nick)는 별명과 학생 이름을 짝짓는다.
짝에서 번호나 별명을 왼쪽, 이름을 오른쪽이라고 한다.
한 장부 안에서 왼쪽 하나는 많아야 한 짝에만 들어 있고, 오른쪽 하나도 많아야 한 짝에만 들어 있다.
두 장부는 서로 영향을 주지 않으며, 처음에는 둘 다 비어 있다.
명령은 "장부 동작 [값]" 모양이고, 장부는 locker 또는 nick이다.
- put a b: 왼쪽이 a인 짝이 있으면 지우고, 오른쪽이 b인 짝이 있으면 지운 다음, a와 b를 새로 짝짓는다.
- get a: 왼쪽이 a인 짝의 오른쪽을 출력한다. 그런 짝이 없으면 -를 출력한다.
- find b: 오른쪽이 b인 짝의 왼쪽을 출력한다. 그런 짝이 없으면 -를 출력한다.
- del a: 왼쪽이 a인 짝이 있으면 지운다.
- drop b: 오른쪽이 b인 짝이 있으면 지운다.
- size: 그 장부에 있는 짝의 수를 출력한다.
첫 줄에 명령 수 q, 다음 q줄에 명령이 하나씩 주어진다.
get, find, size마다 한 줄씩 출력하라.
왼쪽 타입 K와 오른쪽 타입 V를 매개변수로 받는 제네릭 클래스(C++는 클래스 템플릿) BiMap<K, V>를 하나만 만들고, 두 장부를 모두 그 클래스로 만들어 풀어 보자.
같은 짝들을 거꾸로 보는 장부를 돌려주는 메서드 inverse()도 만들어 보자. 그 타입은 BiMap<V, K>이다.
입력
1 ≤ q ≤ 20000. 사물함 번호는 0 이상 1000000000 이하의 정수이고 앞에 쓸데없는 0이 붙지 않는다. 별명과 이름은 영어 소문자 1~10글자다. 한 줄 안의 낱말은 빈칸 하나로 나뉜다. get, find, size 가운데 하나 이상이 주어진다
출력
get, find, size마다 한 줄씩, 명령이 나온 차례대로
예시 1 · stdin
18
locker put 7 ann
locker put 0 bo
nick put ace ann
locker get 7
locker put 7 bo
locker find ann
locker find bo
locker get 0
locker size
locker put 0 cy
locker find cy
locker get 3
locker find dan
locker size
nick find ann
nick drop ann
nick get ace
nick size
stdout
ann
-
7
-
1
0
-
-
2
ace
-
0
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 4개 언어 풀이
이 문제는 제네릭이 있는 TypeScript·Java·C#·C++만 받아요(C++는 클래스 템플릿). Python·JavaScript는 타입을 적지 않으니 클래스 하나가 처음부터 무엇이든 담고(Python의 Generic[K, V]는 적어 둘 뿐 실행할 때 검사하지 않아요), C와 크레이콘에는 타입 매개변수가 없어요. BiMap<K, V>는 사전 두 개(K→V, V→K)를 함께 고쳐요. inverse()는 그 두 사전의 자리를 바꿔 쥔 BiMap<V, K>를 돌려주니, find b는 inverse().get(b), drop b는 inverse().remove(b)가 돼요. 타입 매개변수가 둘이고 그 자리가 바뀌는 것이 요점이에요. 타입 인자를 적는 법은 TS BiMap.create<number, string>(), Java new BiMap<Integer, String>(), C# new BiMap<int, string>(), C++ BiMap<int, string>이에요. Java는 BiMap<int, String>이라 쓰면 컴파일 오류(unexpected type)라서 Integer로 담아요. 왼쪽 타입만 다른 두 장부는 제네릭 함수 run<K> 하나로 처리하고, 문자열을 K로 바꾸는 함수를 함께 넘겨요. '없음'을 돌려주는 법이 언어마다 달라요. TS는 V | undefined, Java는 null, C#은 bool TryGet(K k, out V v), C++은 optional<V>를 썼어요. 함정 하나: put이 옛 짝을 지우지 않으면 낡은 짝이 남아요. 예시의 locker put 7 bo 뒤에 locker find ann이 7, locker get 0이 bo, locker size가 2가 돼요. 함정 둘: TS에서 없음을 x ? String(x) : "-"로 가리면 수 0도 거짓이라, 예시의 locker find cy가 0이 아니라 -가 돼요. x === undefined로 물어요. 함정 셋: C#에서 없으면 default(V)를 돌려주고 null인지로 가리면, V가 int일 때 default는 0이에요. 예시의 locker find ann과 locker find dan이 0으로 나와서 진짜 0번 사물함과 구별할 수 없어요. 함정 넷: Java는 get이 준 null을 String.valueOf로 문자열에 넣으면 - 대신 null이 찍혀요. 함정 다섯: C++ map의 operator[]로 찾으면 없는 키가 기본값과 함께 사전에 생겨요. 기본값이면 없다고 보는 풀이는 예시에서 locker size가 2와 3으로 늘고 locker find cy도 -가 돼요. find로 찾아요.
TypeScriptmain.ts · 68 줄
import { readFileSync } from "node:fs";// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전class BiMap<K, V> { private constructor( private readonly fwd: Map<K, V>, private readonly rev: Map<V, K>, ) {} static create<K, V>(): BiMap<K, V> { return new BiMap<K, V>(new Map<K, V>(), new Map<V, K>()); } // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 inverse(): BiMap<V, K> { return new BiMap<V, K>(this.rev, this.fwd); } get(k: K): V | undefined { return this.fwd.get(k); } remove(k: K): void { const v = this.fwd.get(k); if (v === undefined) return; this.fwd.delete(k); this.rev.delete(v); } put(k: K, v: V): void { this.remove(k); this.inverse().remove(v); this.fwd.set(k, v); this.rev.set(v, k); } get size(): number { return this.fwd.size; }}function show<T>(x: T | undefined): string { return x === undefined ? "-" : String(x);}const out: string[] = [];// 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다function run<K>(m: BiMap<K, string>, parse: (s: string) => K, p: string[]): void { const cmd = p[1]; if (cmd === "put") m.put(parse(p[2]), p[3]); else if (cmd === "get") out.push(show(m.get(parse(p[2])))); else if (cmd === "find") out.push(show(m.inverse().get(p[2]))); else if (cmd === "del") m.remove(parse(p[2])); else if (cmd === "drop") m.inverse().remove(p[2]); else out.push(String(m.size));}const lines: string[] = readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const locker = BiMap.create<number, string>();const nick = BiMap.create<string, string>();for (let i = 1; i <= q; i++) { const p = lines[i].trim().split(/\s+/); if (p[0] === "locker") run(locker, Number, p); else run(nick, (s) => s, p);}console.log(out.join("\n"));
JavaMain.java · 67 줄
import java.io.*;import java.util.*;import java.util.function.Function;// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전class BiMap<K, V> { private final Map<K, V> fwd; private final Map<V, K> rev; BiMap() { this(new HashMap<>(), new HashMap<>()); } private BiMap(Map<K, V> fwd, Map<V, K> rev) { this.fwd = fwd; this.rev = rev; } // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 BiMap<V, K> inverse() { return new BiMap<>(rev, fwd); } // 없으면 null V get(K k) { return fwd.get(k); } void remove(K k) { V v = fwd.remove(k); if (v != null) rev.remove(v); } void put(K k, V v) { remove(k); inverse().remove(v); fwd.put(k, v); rev.put(v, k); } int size() { return fwd.size(); }}public class Main { static StringBuilder sb = new StringBuilder(); static <T> String show(T x) { return x == null ? "-" : x.toString(); } // 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다 static <K> void run(BiMap<K, String> m, Function<String, K> parse, String[] p) { switch (p[1]) { case "put": m.put(parse.apply(p[2]), p[3]); break; case "get": sb.append(show(m.get(parse.apply(p[2])))).append('\n'); break; case "find": sb.append(show(m.inverse().get(p[2]))).append('\n'); break; case "del": m.remove(parse.apply(p[2])); break; case "drop": m.inverse().remove(p[2]); break; default: sb.append(m.size()).append('\n'); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(br.readLine().trim()); BiMap<Integer, String> locker = new BiMap<>(); // int는 타입 인자가 될 수 없어 Integer로 담는다 BiMap<String, String> nick = new BiMap<>(); for (int i = 0; i < q; i++) { String[] p = br.readLine().trim().split(" "); if (p[0].equals("locker")) run(locker, Integer::valueOf, p); else run(nick, s -> s, p); } System.out.print(sb); }}
C#Main.cs · 79 줄
using System;using System.Collections.Generic;using System.Text;// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전class BiMap<K, V>{ private readonly Dictionary<K, V> fwd; private readonly Dictionary<V, K> rev; public BiMap() : this(new Dictionary<K, V>(), new Dictionary<V, K>()) { } private BiMap(Dictionary<K, V> fwd, Dictionary<V, K> rev) { this.fwd = fwd; this.rev = rev; } // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 public BiMap<V, K> Inverse() => new BiMap<V, K>(rev, fwd); // 있는지 없는지를 bool로 돌려주고, 값은 out으로 내보낸다 public bool TryGet(K k, out V v) => fwd.TryGetValue(k, out v); public void Remove(K k) { if (fwd.Remove(k, out V v)) rev.Remove(v); } public void Put(K k, V v) { Remove(k); Inverse().Remove(v); fwd[k] = v; rev[v] = k; } public int Count => fwd.Count;}class Program{ static readonly StringBuilder sb = new StringBuilder(); // 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다 static void Run<K>(BiMap<K, string> m, Func<string, K> parse, string[] p) { switch (p[1]) { case "put": m.Put(parse(p[2]), p[3]); break; case "get": if (m.TryGet(parse(p[2]), out string name)) sb.Append(name); else sb.Append('-'); sb.Append('\n'); break; case "find": if (m.Inverse().TryGet(p[2], out K left)) sb.Append(left); else sb.Append('-'); sb.Append('\n'); break; case "del": m.Remove(parse(p[2])); break; case "drop": m.Inverse().Remove(p[2]); break; default: sb.Append(m.Count).Append('\n'); break; } } static void Main() { var lines = Console.In.ReadToEnd().Split('\n'); int q = int.Parse(lines[0].Trim()); var locker = new BiMap<int, string>(); // int를 포장 없이 그대로 담는다 var nick = new BiMap<string, string>(); for (int i = 1; i <= q; i++) { var p = lines[i].Trim().Split(' '); if (p[0] == "locker") Run(locker, int.Parse, p); else Run(nick, s => s, p); } Console.Write(sb); }}
C++main.cpp · 89 줄
#include <iostream>#include <map>#include <memory>#include <optional>#include <string>using namespace std;// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전template <class K, class V>class BiMap { shared_ptr<map<K, V>> fwd_; shared_ptr<map<V, K>> rev_;public: BiMap() : fwd_(make_shared<map<K, V>>()), rev_(make_shared<map<V, K>>()) {} BiMap(shared_ptr<map<K, V>> fwd, shared_ptr<map<V, K>> rev) : fwd_(std::move(fwd)), rev_(std::move(rev)) {} // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 BiMap<V, K> inverse() const { return BiMap<V, K>(rev_, fwd_); } // find는 없는 키를 만들지 않는다 optional<V> get(const K& k) const { auto it = fwd_->find(k); if (it == fwd_->end()) return nullopt; return it->second; } void remove(const K& k) { auto it = fwd_->find(k); if (it == fwd_->end()) return; rev_->erase(it->second); fwd_->erase(it); } void put(const K& k, const V& v) { remove(k); inverse().remove(v); (*fwd_)[k] = v; (*rev_)[v] = k; } size_t size() const { return fwd_->size(); }};template <class T>void show(const optional<T>& x) { if (x) cout << *x << '\n'; else cout << "-\n";}// 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다template <class K, class Parse>void run(BiMap<K, string>& m, Parse parse, const string& cmd) { string a, b; if (cmd == "put") { cin >> a >> b; m.put(parse(a), b); } else if (cmd == "get") { cin >> a; show(m.get(parse(a))); } else if (cmd == "find") { cin >> b; show(m.inverse().get(b)); } else if (cmd == "del") { cin >> a; m.remove(parse(a)); } else if (cmd == "drop") { cin >> b; m.inverse().remove(b); } else { cout << m.size() << '\n'; }}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; BiMap<int, string> locker; BiMap<string, string> nick; for (int i = 0; i < q; i++) { string ledger, cmd; cin >> ledger >> cmd; if (ledger == "locker") run(locker, [](const string& s) { return stoi(s); }, cmd); else run(nick, [](const string& s) { return s; }, cmd); } return 0;}