You use two lists that remember only the k most recently seen items. One holds integers and the other holds words.
Each list keeps its order so that the most recent item comes first. At first both are empty.
Commands have the form "kind action [value]", where kind is num (the integer list) or word (the word list).
- add x: if the list already has an item equal to x, remove it first. Then put x at the front. If the list then has more than k items, drop the one at the back (the oldest).
- del x: if the list has an item equal to x, remove it. Otherwise do nothing.
- show: print the list's items from the front on one line, separated by single spaces. If the list is empty, print -.
Integers with the same value are equal. Integers in the input may have leading zeros (007 and 7 are equal). When printing, write them in the usual form without leading zeros.
Words are equal only when all their letters are the same.
The first line gives k and the number of commands q, and the next q lines give one command each. Print one line for each show.
Try writing just one generic class Recent<T> (a class template in C++) that takes the item type as a parameter T, and build both the integer list and the word list from that class.
Input
1 ≤ k ≤ 100, 1 ≤ q ≤ 100,000. Integer values are from -10⁹ to 10⁹, and a negative number has a single - in front (0 never does). Integers are written with at most 13 digits. Words are 1 to 10 lowercase English letters. All show commands together print at most 30,000 items.
Output
One line per show
Example 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
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 4 languages
This problem accepts only TypeScript, Java, C# and C++, the languages with generics (class templates in C++). Python and JavaScript do not write types, so a single class holds anything from the start (Python's TypeVar is only written down and not checked at run time), and C and Craykon have no type parameters. The four languages 'find an equal item' differently. TS indexOf searches with ===, so numbers and strings compare by value. Java cannot write Recent<int>, so it stores Recent<Integer> and compares T values with equals. In C#, == on an unconstrained T is a compile error, so use EqualityComparer<T>.Default.Equals; Recent<int> stores ints without boxing. A C++ template generates separate code for each T, and std::find calls that T's ==. Three traps: ① In Java generic code, items.get(i) == x asks whether they are the same object. Integer shares pre-made objects only for -128 to 127, so it looks right for small numbers, but 1000 or a word read from input is a different object even with the same value, so it is not removed and gets in twice. ② In TS and C++, storing the integers as the strings you read, in a Recent<string>, makes 007 and 7 different items and prints 007. Convert with Number(x) or std::stoll and store them in Recent<number> or Recent<long long>. ③ In C#, adding a where T : class constraint so that == compiles does compile, but == inside generic code is a reference comparison, not string's value comparison, so two equal words read from input are seen as different (and it cannot hold int either).
TypeScriptmain.ts · 39 lines
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 lines
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 lines
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 lines
#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;}