1번부터 s번까지 칸 s개가 있는 장부가 있고, 처음에 모든 칸의 값은 0이다.
명령 m개가 차례로 주어지며, 명령은 다음 여섯 가지이다.
'set k v'는 k번 칸의 값을 v로 바꾼다.
'add k v'는 k번 칸의 값에 v를 더한다.
'get k'는 k번 칸의 값을 출력한다.
'save 이름'은 지금 장부의 모습을 기억하는 저장점을 그 이름으로 새로 만든다. 같은 이름의 저장점이 이미 있어도 새로 하나 더 만든다.
'back 이름'은 아직 없어지지 않은 그 이름의 저장점 가운데 가장 나중에 만든 것을 골라, 모든 칸의 값을 그 저장점을 만들 때의 값으로 되돌린다. 그 저장점보다 나중에 만든 저장점은 모두 없어지고, 고른 저장점은 남는다.
'drop 이름'은 아직 없어지지 않은 그 이름의 저장점 가운데 가장 나중에 만든 것을 골라, 그 저장점과 그보다 나중에 만든 저장점을 모두 없앤다. 칸의 값은 바꾸지 않는다.
back과 drop은 일을 마친 뒤 남아 있는 저장점의 수(이름과 상관없이 모두 센 수)를 출력한다.
그 이름의 저장점이 남아 있지 않으면 back과 drop은 아무것도 바꾸지 않고 -1을 출력한다.
출력은 명령이 주어진 차례대로 한 줄에 하나씩 한다.
입력
첫 줄에 s와 m이 빈칸으로 나뉘어 주어진다. 다음 m줄에 명령이 한 줄에 하나씩 주어지며, 낱말 사이는 빈칸 하나이다. 1 ≤ s ≤ 10,000, 1 ≤ m ≤ 10,000, 1 ≤ k ≤ s, -1,000,000,000 ≤ v ≤ 1,000,000,000, 이름은 영어 소문자로만 된 길이 1~8의 문자열. get, back, drop 가운데 하나 이상이 반드시 나온다
출력
get, back, drop 명령마다 한 줄. get은 칸의 값, back과 drop은 남은 저장점의 수 또는 -1. 수는 쉼표 없이 숫자만 쓴다
예시 1 · stdin
3 14
set 1 5
save a
add 1 10
save b
set 2 7
save a
add 2 1
get 2
back a
get 2
drop a
back a
get 1
back b
stdout
8
3
7
2
1
5
-1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
저장점은 나중에 만든 것부터 없어지니 스택이에요. 그런데 저장할 때마다 장부를 통째로 복사하면 칸 10,000개 × 저장 10,000번으로 1억 칸이 돼요. 대신 스택을 하나 더 둬요: 값을 바꿀 때마다 (칸, 바꾸기 전 값)을 기록 스택에 쌓고, 저장점에는 '그때의 기록 길이'만 적어요. back은 기록을 그 길이가 될 때까지 위에서부터 꺼내며 옛 값을 되살려요. 스택 도구는 Python list의 append·pop, JS·TS 배열의 push·pop, C# Stack<T>, C++ vector의 push_back·pop_back(가운데 자리 marks[p]를 읽어야 해서 std::stack은 못 써요), Java와 C는 배열과 개수 변수, 크레이콘은 넣기와 자리빼기(개수 - 1)예요. TS에서는 pop()의 타입이 T | undefined라서 길이를 확인했어도 !를 붙이거나 따로 검사해야 strict 검사를 통과해요. 이름으로 저장점을 찾을 때 스택을 위에서부터 훑으면 느리니, 사전에 '이름 → 가장 위의 자리'를 적고 저장점마다 '같은 이름의 바로 아래 자리'를 적어 둬요. 함정 하나: 기록은 반드시 나중 것부터 되살려요. 같은 칸을 두 번 바꿨을 때 먼저 한 것부터 되살리면 중간 값이 남아요. 함정 둘: back은 고른 저장점을 남기고(같은 이름으로 또 back할 수 있어요), drop은 고른 저장점까지 없애요. 함정 셋: drop은 그 저장점 하나만이 아니라 뒤에 만든 저장점도 함께 없애요. 함정 넷: 같은 이름이 겹치면 가장 나중 것을 찾고, 그것이 없어지면 그 아래 것이 다시 보여야 해요. 저장점을 없앨 때 사전도 함께 고치지 않으면 이미 없어진 저장점을 찾게 돼요. 함정 다섯: 없는 이름을 찾을 때예요. C++ unordered_map의 top[name]은 없는 열쇠에 0을 새로 넣고 돌려줘서 0번 저장점이 있는 것처럼 보여요. find를 써요. Python top[name]은 KeyError(get(name, -1)), Java get은 null(getOrDefault), C#의 top[name]은 KeyNotFoundException(TryGetValue), JS·TS Map.get은 undefined(?? -1), 크레이콘은 있나로 먼저 물어요. C에는 사전이 없어 해시 표를 직접 짜요. 함정 여섯: 10억을 여러 번 더하면 32비트를 넘어요. Java·C#의 int는 오류 없이 돌아서 엉뚱한 수가 되고 C·C++은 정의되지 않은 동작이니 long·long long을 써요. Python 정수는 한계가 없고 JS·TS·크레이콘의 수는 2^53까지 정확해요.
Pythonmain.py · 53 줄
import sysdef main(): lines = sys.stdin.read().split("\n") s, m = map(int, lines[0].split()) val = [0] * (s + 1) log = [] # 되돌리기 기록 스택: (칸, 바꾸기 전 값) names = [] # 저장점 스택: 이름 marks = [] # 저장점 스택: 저장할 때의 기록 길이 below = [] # 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1) top = {} # 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리 def cut(size): """저장점 스택을 size개만 남기고 위에서부터 없앤다.""" while len(names) > size: top[names.pop()] = below.pop() marks.pop() out = [] for line in lines[1 : 1 + m]: t = line.split() cmd = t[0] if cmd == "set" or cmd == "add": k, x = int(t[1]), int(t[2]) log.append((k, val[k])) val[k] = x if cmd == "set" else val[k] + x elif cmd == "get": out.append(val[int(t[1])]) elif cmd == "save": below.append(top.get(t[1], -1)) top[t[1]] = len(names) names.append(t[1]) marks.append(len(log)) else: p = top.get(t[1], -1) if p == -1: out.append(-1) elif cmd == "back": # 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다 while len(log) > marks[p]: k, old = log.pop() val[k] = old cut(p + 1) # 그 저장점은 남는다 out.append(p + 1) else: # drop cut(p) # 그 저장점까지 없앤다(값은 그대로) out.append(p) print("\n".join(map(str, out)))main()
JavaScriptmain.js · 52 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [s, m] = lines[0].trim().split(/\s+/).map(Number);const val = new Array(s + 1).fill(0);const logSlot = []; // 되돌리기 기록 스택: 칸const logOld = []; // 되돌리기 기록 스택: 바꾸기 전 값const names = []; // 저장점 스택: 이름const marks = []; // 저장점 스택: 저장할 때의 기록 길이const below = []; // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)const top = new Map(); // 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리// 저장점 스택을 size개만 남기고 위에서부터 없앤다function cut(size) { while (names.length > size) { top.set(names.pop(), below.pop()); marks.pop(); }}const out = [];for (let i = 1; i <= m; i++) { const t = lines[i].trim().split(/\s+/); const cmd = t[0]; if (cmd === "set" || cmd === "add") { const k = Number(t[1]); const x = Number(t[2]); logSlot.push(k); logOld.push(val[k]); val[k] = cmd === "set" ? x : val[k] + x; } else if (cmd === "get") { out.push(val[Number(t[1])]); } else if (cmd === "save") { below.push(top.has(t[1]) ? top.get(t[1]) : -1); top.set(t[1], names.length); names.push(t[1]); marks.push(logSlot.length); } else { const p = top.has(t[1]) ? top.get(t[1]) : -1; if (p === -1) { out.push(-1); } else if (cmd === "back") { // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다 while (logSlot.length > marks[p]) val[logSlot.pop()] = logOld.pop(); cut(p + 1); // 그 저장점은 남는다 out.push(p + 1); } else { cut(p); // drop: 그 저장점까지 없앤다(값은 그대로) out.push(p); } }}console.log(out.join("\n"));
TypeScriptmain.ts · 55 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [s, m] = lines[0].trim().split(/\s+/).map(Number);const val: number[] = new Array<number>(s + 1).fill(0);const logSlot: number[] = []; // 되돌리기 기록 스택: 칸const logOld: number[] = []; // 되돌리기 기록 스택: 바꾸기 전 값const names: string[] = []; // 저장점 스택: 이름const marks: number[] = []; // 저장점 스택: 저장할 때의 기록 길이const below: number[] = []; // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)const top = new Map<string, number>(); // 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리// 저장점 스택을 size개만 남기고 위에서부터 없앤다function cut(size: number): void { while (names.length > size) { // pop()의 타입은 `T | undefined`다. 길이를 확인했으니 !로 undefined가 아님을 알린다 top.set(names.pop()!, below.pop()!); marks.pop(); }}const out: number[] = [];for (let i = 1; i <= m; i++) { const t = lines[i].trim().split(/\s+/); const cmd = t[0]; if (cmd === "set" || cmd === "add") { const k = Number(t[1]); const x = Number(t[2]); logSlot.push(k); logOld.push(val[k]); val[k] = cmd === "set" ? x : val[k] + x; } else if (cmd === "get") { out.push(val[Number(t[1])]); } else if (cmd === "save") { below.push(top.get(t[1]) ?? -1); top.set(t[1], names.length); names.push(t[1]); marks.push(logSlot.length); } else { const p = top.get(t[1]) ?? -1; if (p === -1) { out.push(-1); } else if (cmd === "back") { // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다 while (logSlot.length > marks[p]) val[logSlot.pop()!] = logOld.pop()!; cut(p + 1); // 그 저장점은 남는다 out.push(p + 1); } else { cut(p); // drop: 그 저장점까지 없앤다(값은 그대로) out.push(p); } }}console.log(out.join("\n"));
JavaMain.java · 76 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashMap;import java.util.StringTokenizer;public class Main { static String[] names; // 저장점 스택: 이름 static int[] marks; // 저장점 스택: 저장할 때의 기록 길이 static int[] below; // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1) static int count = 0; // 살아 있는 저장점 수 static HashMap<String, Integer> top = new HashMap<>(); // 이름 → 가장 위의 자리 // 저장점 스택을 size개만 남기고 위에서부터 없앤다 static void cut(int size) { while (count > size) { count--; top.put(names[count], below[count]); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int s = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); long[] val = new long[s + 1]; // add가 쌓이면 int를 넘는다 int[] logSlot = new int[m]; // 되돌리기 기록 스택: 칸 long[] logOld = new long[m]; // 되돌리기 기록 스택: 바꾸기 전 값 int logSize = 0; names = new String[m]; marks = new int[m]; below = new int[m]; StringBuilder sb = new StringBuilder(); for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); String cmd = st.nextToken(); if (cmd.equals("set") || cmd.equals("add")) { int k = Integer.parseInt(st.nextToken()); long x = Long.parseLong(st.nextToken()); logSlot[logSize] = k; logOld[logSize] = val[k]; logSize++; val[k] = cmd.equals("set") ? x : val[k] + x; } else if (cmd.equals("get")) { sb.append(val[Integer.parseInt(st.nextToken())]).append('\n'); } else if (cmd.equals("save")) { String name = st.nextToken(); below[count] = top.getOrDefault(name, -1); top.put(name, count); names[count] = name; marks[count] = logSize; count++; } else { int p = top.getOrDefault(st.nextToken(), -1); if (p == -1) { sb.append(-1).append('\n'); } else if (cmd.equals("back")) { // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다 while (logSize > marks[p]) { logSize--; val[logSlot[logSize]] = logOld[logSize]; } cut(p + 1); // 그 저장점은 남는다 sb.append(p + 1).append('\n'); } else { cut(p); // drop: 그 저장점까지 없앤다(값은 그대로) sb.append(p).append('\n'); } } } System.out.print(sb); }}
C#Main.cs · 83 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int s = int.Parse(first[0]); int m = int.Parse(first[1]); long[] val = new long[s + 1]; // add가 쌓이면 int를 넘는다 var log = new Stack<(int Slot, long Old)>(); // 되돌리기 기록: (칸, 바꾸기 전 값) var names = new List<string>(); // 저장점 스택: 이름 var marks = new List<int>(); // 저장점 스택: 저장할 때의 기록 길이 var below = new List<int>(); // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1) var top = new Dictionary<string, int>(); // 이름 → 가장 위의 자리 // 저장점 스택을 size개만 남기고 위에서부터 없앤다 void Cut(int size) { while (names.Count > size) { int last = names.Count - 1; top[names[last]] = below[last]; names.RemoveAt(last); marks.RemoveAt(last); below.RemoveAt(last); } } var sb = new StringBuilder(); for (int i = 0; i < m; i++) { string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); string cmd = t[0]; if (cmd == "set" || cmd == "add") { int k = int.Parse(t[1]); long x = long.Parse(t[2]); log.Push((k, val[k])); val[k] = cmd == "set" ? x : val[k] + x; } else if (cmd == "get") { sb.Append(val[int.Parse(t[1])]).Append('\n'); } else if (cmd == "save") { below.Add(top.TryGetValue(t[1], out int under) ? under : -1); top[t[1]] = names.Count; names.Add(t[1]); marks.Add(log.Count); } else { int p = top.TryGetValue(t[1], out int found) ? found : -1; if (p == -1) { sb.Append(-1).Append('\n'); } else if (cmd == "back") { // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다 while (log.Count > marks[p]) { var (k, old) = log.Pop(); val[k] = old; } Cut(p + 1); // 그 저장점은 남는다 sb.Append(p + 1).Append('\n'); } else { Cut(p); // drop: 그 저장점까지 없앤다(값은 그대로) sb.Append(p).Append('\n'); } } } Console.Write(sb); }}
C++main.cpp · 72 줄
#include <iostream>#include <string>#include <unordered_map>#include <utility>#include <vector>using namespace std;vector<string> names; // 저장점 스택: 이름vector<int> marks; // 저장점 스택: 저장할 때의 기록 길이vector<int> below; // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)unordered_map<string, int> top; // 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리// 저장점 스택을 size개만 남기고 위에서부터 없앤다void cut(size_t size) { while (names.size() > size) { top[names.back()] = below.back(); names.pop_back(); marks.pop_back(); below.pop_back(); }}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int s, m; cin >> s >> m; vector<long long> val(s + 1, 0); // add가 쌓이면 int를 넘는다 vector<pair<int, long long>> log; // 되돌리기 기록 스택: (칸, 바꾸기 전 값) for (int i = 0; i < m; i++) { string cmd; cin >> cmd; if (cmd == "set" || cmd == "add") { int k; long long x; cin >> k >> x; log.push_back({k, val[k]}); val[k] = cmd == "set" ? x : val[k] + x; } else if (cmd == "get") { int k; cin >> k; cout << val[k] << '\n'; } else { string name; cin >> name; auto it = top.find(name); int p = it == top.end() ? -1 : it->second; if (cmd == "save") { below.push_back(p); top[name] = (int)names.size(); names.push_back(name); marks.push_back((int)log.size()); } else if (p == -1) { cout << -1 << '\n'; } else if (cmd == "back") { // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다 while ((int)log.size() > marks[p]) { val[log.back().first] = log.back().second; log.pop_back(); } cut(p + 1); // 그 저장점은 남는다 cout << p + 1 << '\n'; } else { cut(p); // drop: 그 저장점까지 없앤다(값은 그대로) cout << p << '\n'; } } } return 0;}
Cmain.c · 91 줄
#include <stdio.h>#include <stdlib.h>#include <string.h>#define TABLE 32768 // 이름은 많아야 10,000가지라 넉넉하다(2의 거듭제곱)// 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리(해시 표, 빈칸은 이름이 "")static char keys[TABLE][9];static int tops[TABLE];// 이름이 들어 있는(또는 들어갈) 칸을 찾는다static int find(const char *name) { unsigned h = 2166136261u; for (const char *p = name; *p; p++) h = (h ^ (unsigned char)*p) * 16777619u; int i = (int)(h & (TABLE - 1)); while (keys[i][0] != '\0' && strcmp(keys[i], name) != 0) i = (i + 1) & (TABLE - 1); return i;}static int *name_cell; // 저장점 스택: 이름이 든 해시 표의 칸static int *marks; // 저장점 스택: 저장할 때의 기록 길이static int *below; // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)static int count = 0; // 살아 있는 저장점 수// 저장점 스택을 size개만 남기고 위에서부터 없앤다static void cut(int size) { while (count > size) { count--; tops[name_cell[count]] = below[count]; }}int main(void) { int s, m; if (scanf("%d %d", &s, &m) != 2) return 1; long long *val = calloc(s + 1, sizeof(long long)); // add가 쌓이면 int를 넘는다 int *log_slot = malloc(sizeof(int) * m); // 되돌리기 기록 스택: 칸 long long *log_old = malloc(sizeof(long long) * m); // 되돌리기 기록 스택: 바꾸기 전 값 int log_size = 0; name_cell = malloc(sizeof(int) * m); marks = malloc(sizeof(int) * m); below = malloc(sizeof(int) * m); for (int i = 0; i < m; i++) { char cmd[8]; scanf("%7s", cmd); if (strcmp(cmd, "set") == 0 || strcmp(cmd, "add") == 0) { int k; long long x; scanf("%d %lld", &k, &x); log_slot[log_size] = k; log_old[log_size] = val[k]; log_size++; val[k] = cmd[0] == 's' ? x : val[k] + x; } else if (strcmp(cmd, "get") == 0) { int k; scanf("%d", &k); printf("%lld\n", val[k]); } else { char name[9]; scanf("%8s", name); int cell = find(name); int p = keys[cell][0] == '\0' ? -1 : tops[cell]; if (strcmp(cmd, "save") == 0) { if (keys[cell][0] == '\0') strcpy(keys[cell], name); below[count] = p; tops[cell] = count; name_cell[count] = cell; marks[count] = log_size; count++; } else if (p == -1) { printf("-1\n"); } else if (strcmp(cmd, "back") == 0) { // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다 while (log_size > marks[p]) { log_size--; val[log_slot[log_size]] = log_old[log_size]; } cut(p + 1); // 그 저장점은 남는다 printf("%d\n", p + 1); } else { cut(p); // drop: 그 저장점까지 없앤다(값은 그대로) printf("%d\n", p); } } } free(val); free(log_slot); free(log_old); free(name_cell); free(marks); free(below); return 0;}
Craykonmain.cray · 86 줄
첫줄 = 콘솔.수들읽기();s = 첫줄[0];m = 첫줄[1];val = 새목록(s, 0); // 칸 k는 val[k - 1]에 둔다logSlot = []; // 되돌리기 기록 스택: 칸logOld = []; // 되돌리기 기록 스택: 바꾸기 전 값names = []; // 저장점 스택: 이름marks = []; // 저장점 스택: 저장할 때의 기록 길이below = []; // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)top = 사전(); // 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리반복 (i = 0; i < m; i++){ t = 콘솔.줄읽기().공백제거().나누기(); cmd = t[0]; 만약 (cmd == "set" || cmd == "add") { k = t[1].수로변환() - 1; x = t[2].수로변환(); logSlot.넣기(k); logOld.넣기(val[k]); 만약 (cmd == "set") { val[k] = x; } 아니면 { val[k] = val[k] + x; } } 아니면 만약 (cmd == "get") { 콘솔.쓰기(val[t[1].수로변환() - 1]); } 아니면 { p = -1; 만약 (top.있나(t[1])) { p = top[t[1]]; } 만약 (cmd == "save") { below.넣기(p); top[t[1]] = names.개수; names.넣기(t[1]); marks.넣기(logSlot.개수); } 아니면 만약 (p == -1) { 콘솔.쓰기(-1); } 아니면 만약 (cmd == "back") { // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다 동안 (logSlot.개수 > marks[p]) { 끝 = logSlot.개수 - 1; val[logSlot[끝]] = logOld[끝]; logSlot.자리빼기(끝); logOld.자리빼기(끝); } 자르기(p + 1); // 그 저장점은 남는다 콘솔.쓰기(p + 1); } 아니면 { 자르기(p); // drop: 그 저장점까지 없앤다(값은 그대로) 콘솔.쓰기(p); } }}// 저장점 스택을 size개만 남기고 위에서부터 없앤다자르기(size){ 동안 (names.개수 > size) { 끝 = names.개수 - 1; top[names[끝]] = below[끝]; names.자리빼기(끝); marks.자리빼기(끝); below.자리빼기(끝); }}