최근에 본 것을 k개까지만 기억하는 목록을 두 개 쓴다. 하나는 정수를, 하나는 낱말을 담는다.
목록은 가장 최근 것이 맨 앞에 오도록 차례를 지킨다. 처음에는 둘 다 비어 있다.
명령은 "종류 동작 [값]" 모양이고, 종류는 num(정수 목록) 또는 word(낱말 목록)이다.
- add x: 목록에 x와 같은 것이 이미 있으면 먼저 그것을 뺀다. 그다음 x를 맨 앞에 넣는다. 그 결과 항목이 k개를 넘으면 맨 뒤(가장 오래된 것) 하나를 버린다.
- del x: 목록에 x와 같은 것이 있으면 뺀다. 없으면 아무것도 하지 않는다.
- show: 목록의 항목을 맨 앞부터 빈칸 하나씩 띄워 한 줄로 출력한다. 목록이 비었으면 -를 출력한다.
정수는 값이 같으면 같은 것이다. 입력의 정수는 앞에 0이 붙어 있을 수 있다(007과 7은 같다). 출력할 때는 앞의 0 없이 보통 모양으로 쓴다.
낱말은 글자가 모두 같아야 같은 것이다.
첫 줄에 k와 명령 수 q, 다음 q줄에 명령이 하나씩 주어진다. show마다 한 줄씩 출력하라.
항목의 타입을 매개변수 T로 받는 제네릭 클래스(C++는 클래스 템플릿) Recent<T>를 하나만 만들고, 정수 목록과 낱말 목록을 모두 그 클래스로 만들어 풀어 보자.
입력
1 ≤ k ≤ 100, 1 ≤ q ≤ 100,000. 정수의 값은 -10⁹ 이상 10⁹ 이하이고, 음수는 - 하나가 앞에 붙는다(0에는 붙지 않는다). 정수는 숫자 13개 이하로 쓴다. 낱말은 영어 소문자 1~10자다. show가 출력하는 항목은 모두 합쳐 30,000개 이하다.
출력
show마다 한 줄
예시 1 · stdin
3 13
num add 5
word add kiwi
num add 0012
num add 300
num add 5
num add 7
word add fig
word add kiwi
num del 300
num show
word show
word del plum
word show
stdout
7 5
kiwi fig
kiwi fig
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 4개 언어 풀이
이 문제는 제네릭이 있는 TypeScript·Java·C#·C++만 받아요(C++는 클래스 템플릿). Python·JavaScript는 타입을 적지 않으니 클래스 하나가 처음부터 무엇이든 담고(Python의 TypeVar는 적어 둘 뿐 실행할 때 검사하지 않아요), C와 크레이콘에는 타입 매개변수가 없어요. 네 언어는 '같은 것 찾기'를 다르게 해요. TS indexOf는 ===로 찾아서 수와 문자열이 값으로 비교돼요. Java는 Recent<int>를 못 써서 Recent<Integer>로 담고, T끼리는 equals로 비교해요. C#은 제약 없는 T에 ==를 쓰면 컴파일 오류라서 EqualityComparer<T>.Default.Equals를 쓰고, Recent<int>는 포장(boxing) 없이 담아요. C++ 템플릿은 T마다 코드가 따로 만들어지고 std::find가 그 T의 ==를 불러요. 함정 셋: ① Java 제네릭 코드에서 items.get(i) == x는 같은 객체인지를 물어요. Integer는 -128~127만 미리 만들어 둔 객체를 함께 써서 작은 수에서는 맞는 것처럼 보이지만, 1000이나 읽어 들인 낱말은 값이 같아도 다른 객체라 빠지지 않고 두 번 들어가요. ② TS·C++에서 정수를 읽은 문자열 그대로 Recent<string>에 담으면 007과 7이 다른 항목이 되고, 출력도 007로 나와요. Number(x)·std::stoll로 바꿔 Recent<number>·Recent<long long>에 담아요. ③ C#에서 ==를 쓰려고 where T : class 제약을 걸면 컴파일은 되지만, 제네릭 안의 ==는 string의 값 비교가 아니라 참조 비교라 읽어 들인 같은 낱말을 다르다고 봐요(게다가 int는 못 담아요).
TypeScriptmain.ts · 39 줄
import { readFileSync } from "node:fs";// 가장 최근 것부터 k개까지만 기억하는 목록. T가 무엇이든 같은 코드로 쓴다class Recent<T> { private items: T[] = []; constructor(private readonly capacity: number) {} add(x: T): void { this.remove(x); // 이미 있으면 빼고 this.items.unshift(x); // 맨 앞(가장 최근)에 넣고 if (this.items.length > this.capacity) this.items.pop(); // 넘치면 가장 오래된 것을 버린다 } remove(x: T): void { const i = this.items.indexOf(x); // indexOf는 ===로 찾는다: 수와 문자열은 값으로 같다 if (i >= 0) this.items.splice(i, 1); } show(): string { return this.items.length === 0 ? "-" : this.items.join(" "); }}const lines = readFileSync(0, "utf8").split("\n");const [k, q] = lines[0].split(" ").map(Number);const nums = new Recent<number>(k); // 수는 수로 바꿔 담아야 "007"과 "7"이 같아진다const words = new Recent<string>(k);const out: string[] = [];for (const line of lines.slice(1, 1 + q)) { const [kind, cmd, arg] = line.trim().split(" "); if (kind === "num") { if (cmd === "show") out.push(nums.show()); else if (cmd === "add") nums.add(Number(arg)); else nums.remove(Number(arg)); } else { if (cmd === "show") out.push(words.show()); else if (cmd === "add") words.add(arg); else words.remove(arg); }}console.log(out.join("\n"));
JavaMain.java · 63 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;// 가장 최근 것부터 capacity개까지만 기억하는 목록. T가 무엇이든 같은 코드로 쓴다class Recent<T> { private final List<T> items = new ArrayList<>(); private final int capacity; Recent(int capacity) { this.capacity = capacity; } void add(T x) { remove(x); items.add(0, x); if (items.size() > capacity) items.remove(items.size() - 1); } void remove(T x) { // T는 객체라서 ==는 같은 객체인지를 묻는다. 값이 같은지는 equals로 묻는다 for (int i = 0; i < items.size(); i++) { if (items.get(i).equals(x)) { items.remove(i); return; } } } String show() { if (items.isEmpty()) return "-"; StringBuilder sb = new StringBuilder(); for (T x : items) { if (sb.length() > 0) sb.append(' '); sb.append(x); } return sb.toString(); }}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 k = Integer.parseInt(first[0]), q = Integer.parseInt(first[1]); Recent<Integer> nums = new Recent<>(k); // Recent<int>는 안 된다: 제네릭에는 Integer로 담는다 Recent<String> words = new Recent<>(k); StringBuilder out = new StringBuilder(); for (int e = 0; e < q; e++) { String[] p = br.readLine().trim().split(" "); boolean isNum = p[0].equals("num"); if (p[1].equals("show")) { out.append(isNum ? nums.show() : words.show()).append('\n'); } else if (isNum) { int x = Integer.parseInt(p[2]); // "007"도 7로 읽힌다 if (p[1].equals("add")) nums.add(x); else nums.remove(x); } else { if (p[1].equals("add")) words.add(p[2]); else words.remove(p[2]); } } System.out.print(out); }}
C#Main.cs · 57 줄
using System;using System.Collections.Generic;using System.IO;using System.Text;// 가장 최근 것부터 capacity개까지만 기억하는 목록. T가 무엇이든 같은 코드로 쓴다class Recent<T>{ private readonly List<T> items = new List<T>(); private readonly int capacity; // 제약 없는 T에는 ==를 쓸 수 없다(컴파일 오류). 그 T에 맞는 같음은 EqualityComparer가 안다 private static readonly EqualityComparer<T> Same = EqualityComparer<T>.Default; public Recent(int capacity) { this.capacity = capacity; } public void Add(T x) { Remove(x); items.Insert(0, x); if (items.Count > capacity) items.RemoveAt(items.Count - 1); } public void Remove(T x) { int i = items.FindIndex(y => Same.Equals(y, x)); if (i >= 0) items.RemoveAt(i); } public string Show() => items.Count == 0 ? "-" : string.Join(" ", items);}class Program{ static void Main() { var input = Console.In; string[] first = input.ReadLine()!.Trim().Split(' '); int k = int.Parse(first[0]), q = int.Parse(first[1]); var nums = new Recent<int>(k); // C# 제네릭은 int를 포장(boxing) 없이 담는다 var words = new Recent<string>(k); var sb = new StringBuilder(); for (int e = 0; e < q; e++) { string[] p = input.ReadLine()!.Trim().Split(' '); bool isNum = p[0] == "num"; if (p[1] == "show") sb.Append(isNum ? nums.Show() : words.Show()).Append('\n'); else if (isNum) { int x = int.Parse(p[2]); // "007"도 7로 읽힌다 if (p[1] == "add") nums.Add(x); else nums.Remove(x); } else if (p[1] == "add") words.Add(p[2]); else words.Remove(p[2]); } Console.Write(sb); }}
C++main.cpp · 59 줄
#include <algorithm>#include <deque>#include <iostream>#include <sstream>#include <string>// 가장 최근 것부터 capacity개까지만 기억하는 목록. 템플릿이라 T마다 따로 만들어진다template <typename T>class Recent {public: explicit Recent(std::size_t capacity) : capacity_(capacity) {} void add(const T &x) { remove(x); items_.push_front(x); if (items_.size() > capacity_) items_.pop_back(); } void remove(const T &x) { auto it = std::find(items_.begin(), items_.end(), x); // T의 ==로 찾는다 if (it != items_.end()) items_.erase(it); } std::string show() const { if (items_.empty()) return "-"; std::ostringstream os; for (std::size_t i = 0; i < items_.size(); i++) os << (i ? " " : "") << items_[i]; return os.str(); }private: std::deque<T> items_; std::size_t capacity_;};int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::size_t k; int q; std::cin >> k >> q; Recent<long long> nums(k); // 수는 수로 읽어야 "007"과 "7"이 같아진다 Recent<std::string> words(k); std::string kind, cmd, arg; std::string out; for (int e = 0; e < q; e++) { std::cin >> kind >> cmd; if (cmd == "show") { out += (kind == "num" ? nums.show() : words.show()) + '\n'; continue; } std::cin >> arg; if (kind == "num") { long long x = std::stoll(arg); if (cmd == "add") nums.add(x); else nums.remove(x); } else { if (cmd == "add") words.add(arg); else words.remove(arg); } } std::cout << out;}