처음에 비어 있는 문자열 하나를 고치는 명령 m개가 차례로 주어진다.
명령은 다음 네 가지이다.
'type s'는 문자열 끝에 s를 붙인다.
'erase k'는 문자열 끝에서 k글자를 지운다. 문자열이 k글자보다 짧으면 있는 글자를 모두 지운다.
'undo'는 되돌릴 수 있는 편집 가운데 가장 나중에 하거나 다시 한 것을 되돌린다.
'redo'는 다시 할 수 있는 편집 가운데 가장 나중에 되돌린 것을 다시 한다.
여기서 편집은 type과, 실제로 한 글자 이상 지운 erase를 말한다.
문자열이 비어 있을 때의 erase는 아무 일도 하지 않으며 편집으로 치지 않는다.
편집을 하면 그 편집은 되돌릴 수 있는 편집이 된다.
undo로 되돌린 편집은 더 이상 되돌릴 수 없고, 다시 할 수 있는 편집이 된다.
redo로 다시 한 편집은 더 이상 다시 할 수 없고, 다시 되돌릴 수 있는 편집이 된다.
되돌린 erase를 되돌리면 그때 지웠던 글자들을 끝에 다시 붙이고, 다시 하면 같은 글자 수를 끝에서 다시 지운다.
새 편집(type 또는 글자를 지운 erase)을 하면, 그때까지 다시 할 수 있던 편집은 모두 사라진다.
undo와 redo는 새 편집이 아니므로 다시 할 수 있는 편집을 지우지 않는다.
되돌릴 편집이 없을 때의 undo와 다시 할 편집이 없을 때의 redo는 아무 일도 하지 않는다.
명령을 모두 마친 뒤의 문자열을 출력하라.
문자열이 비어 있으면 EMPTY를 출력한다.
입력
첫 줄에 m, 다음 m줄에 줄마다 명령 하나가 주어진다. 1 ≤ m ≤ 10,000. type의 s는 영어 소문자 1~5글자, erase의 k는 1 이상 100 이하의 정수이다.
출력
마지막 문자열(영어 소문자) 또는 EMPTY
예시 1 · stdin
7
type hello
erase 2
type p
undo
undo
redo
type y
stdout
hely
예시 2 · stdin
5
type ab
undo
erase 3
redo
redo
stdout
ab
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
되돌리기와 다시 하기는 스택 두 개예요. 편집을 하면 되돌리기 스택에 쌓고, undo는 그 스택 맨 위를 꺼내 되돌린 뒤 다시 하기 스택에 쌓고, redo는 거꾸로 해요. 가장 나중에 한 것을 가장 먼저 꺼내니(LIFO) 스택이 딱 맞아요. 편집을 '무엇을 했는지'로 적어 두는 게 요령이에요: type은 붙인 문자열을, erase는 실제로 지운 문자열을 적어 둬야 되돌릴 때 다시 붙일 수 있어요(요청한 k가 아니라 지운 글자 수만큼). 흔한 함정은 셋이에요. ① 새 편집을 하고도 다시 하기 스택을 비우지 않으면, 갈라진 옛 기록이 redo로 되살아나요. ② 빈 문자열에서 erase를 편집으로 기록하면, 아무것도 안 한 명령이 다시 하기 스택을 지우고 undo 한 번을 헛되이 먹어요. ③ redo한 편집을 되돌리기 스택에 돌려놓지 않으면 그 편집은 다시 되돌릴 수 없어요. 언어마다 스택과 문자열 다루는 법이 달라요. Python은 목록 append/pop과 글자 목록(text.extend(s), del text[len(text) - k:]), Java는 ArrayDeque<Edit>(push/pop)와 record Edit(boolean typed, String s), StringBuilder.setLength로 끝을 잘라요. C#은 Stack<Edit>의 TryPop(out var e)가 빈 스택을 알아서 걸러 주고, StringBuilder.Length -= k로 잘라요. C++은 std::stack(꺼내려면 top() 다음 pop() 두 번)과 std::string::erase, 비우기는 redo = {}예요. C는 편집을 구조체 배열에 두고 두 스택에는 번호만 넣으며, 문자열은 고정 버퍼와 길이 변수로 다뤄 끝 자르기가 길이만 줄이면 돼요. JavaScript·TypeScript는 배열 push/pop(빈 배열의 pop()은 undefined)과 slice, 비우기는 length = 0이에요. 크레이콘은 편집을 ["type", s] 같은 목록으로 담고, 스택은 넣기와 자리빼기(개수 - 1), 비우기는 비우기(), 끝 자르기는 text.부분문자열(0, text.길이 - k)예요.
Pythonmain.py · 50 줄
import syslines = sys.stdin.read().split("\n")m = int(lines[0])text = [] # 지금 문자열(글자 목록: 끝에 붙이고 끝에서 지우기가 빠르다)undo = [] # 되돌릴 수 있는 편집들: ("type", 붙인 문자열) 또는 ("erase", 지운 문자열)redo = [] # 되돌렸다가 다시 할 수 있는 편집들def do(kind, s): if kind == "type": text.extend(s) else: del text[len(text) - len(s):]def undo_edit(kind, s): if kind == "type": del text[len(text) - len(s):] else: text.extend(s)for line in lines[1:1 + m]: parts = line.split() cmd = parts[0] if cmd == "type": do("type", parts[1]) undo.append(("type", parts[1])) redo.clear() # 새 편집을 하면 다시 하기 목록은 사라진다 elif cmd == "erase": k = min(int(parts[1]), len(text)) if k == 0: continue # 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) removed = "".join(text[len(text) - k:]) do("erase", removed) undo.append(("erase", removed)) redo.clear() elif cmd == "undo": if undo: edit = undo.pop() undo_edit(*edit) redo.append(edit) elif cmd == "redo": if redo: edit = redo.pop() do(*edit) undo.append(edit)print("".join(text) if text else "EMPTY")
JavaScriptmain.js · 45 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const m = Number(lines[0]);let text = "";const undo = []; // 되돌릴 수 있는 편집들: { kind: "type" | "erase", s: 붙이거나 지운 문자열 }const redo = []; // 되돌렸다가 다시 할 수 있는 편집들function apply(edit) { if (edit.kind === "type") text += edit.s; else text = text.slice(0, text.length - edit.s.length);}function revert(edit) { if (edit.kind === "type") text = text.slice(0, text.length - edit.s.length); else text += edit.s;}for (let i = 1; i <= m; i++) { const [cmd, arg] = lines[i].trim().split(" "); if (cmd === "type") { const edit = { kind: "type", s: arg }; apply(edit); undo.push(edit); redo.length = 0; // 새 편집을 하면 다시 하기 목록은 사라진다 } else if (cmd === "erase") { const k = Math.min(Number(arg), text.length); if (k === 0) continue; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) const edit = { kind: "erase", s: text.slice(text.length - k) }; apply(edit); undo.push(edit); redo.length = 0; } else if (cmd === "undo") { const edit = undo.pop(); if (edit !== undefined) { revert(edit); redo.push(edit); } } else if (cmd === "redo") { const edit = redo.pop(); if (edit !== undefined) { apply(edit); undo.push(edit); } }}console.log(text.length > 0 ? text : "EMPTY");
TypeScriptmain.ts · 52 줄
import { readFileSync } from "node:fs";interface Edit { kind: "type" | "erase"; s: string; // 붙이거나 지운 문자열}const lines: string[] = readFileSync(0, "utf8").split("\n");const m = Number(lines[0]);let text = "";const undo: Edit[] = []; // 되돌릴 수 있는 편집들const redo: Edit[] = []; // 되돌렸다가 다시 할 수 있는 편집들function apply(edit: Edit): void { if (edit.kind === "type") text += edit.s; else text = text.slice(0, text.length - edit.s.length);}function revert(edit: Edit): void { if (edit.kind === "type") text = text.slice(0, text.length - edit.s.length); else text += edit.s;}for (let i = 1; i <= m; i++) { const [cmd, arg] = lines[i].trim().split(" "); if (cmd === "type") { const edit: Edit = { kind: "type", s: arg }; apply(edit); undo.push(edit); redo.length = 0; // 새 편집을 하면 다시 하기 목록은 사라진다 } else if (cmd === "erase") { const k = Math.min(Number(arg), text.length); if (k === 0) continue; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) const edit: Edit = { kind: "erase", s: text.slice(text.length - k) }; apply(edit); undo.push(edit); redo.length = 0; } else if (cmd === "undo") { const edit = undo.pop(); if (edit !== undefined) { revert(edit); redo.push(edit); } } else if (cmd === "redo") { const edit = redo.pop(); if (edit !== undefined) { apply(edit); undo.push(edit); } }}console.log(text.length > 0 ? text : "EMPTY");
JavaMain.java · 62 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;public class Main { // 편집 하나: 붙였는지(type) 지웠는지(erase)와 그 문자열 record Edit(boolean typed, String s) {} static StringBuilder text = new StringBuilder(); static void apply(Edit e) { if (e.typed()) text.append(e.s()); else text.setLength(text.length() - e.s().length()); } static void revert(Edit e) { if (e.typed()) text.setLength(text.length() - e.s().length()); else text.append(e.s()); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int m = Integer.parseInt(in.readLine().trim()); ArrayDeque<Edit> undo = new ArrayDeque<>(); // 되돌릴 수 있는 편집들 ArrayDeque<Edit> redo = new ArrayDeque<>(); // 되돌렸다가 다시 할 수 있는 편집들 for (int i = 0; i < m; i++) { String[] parts = in.readLine().trim().split(" "); switch (parts[0]) { case "type" -> { Edit e = new Edit(true, parts[1]); apply(e); undo.push(e); redo.clear(); // 새 편집을 하면 다시 하기 목록은 사라진다 } case "erase" -> { int k = Math.min(Integer.parseInt(parts[1]), text.length()); if (k == 0) continue; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) Edit e = new Edit(false, text.substring(text.length() - k)); apply(e); undo.push(e); redo.clear(); } case "undo" -> { if (!undo.isEmpty()) { Edit e = undo.pop(); revert(e); redo.push(e); } } case "redo" -> { if (!redo.isEmpty()) { Edit e = redo.pop(); apply(e); undo.push(e); } } } } System.out.println(text.length() > 0 ? text : "EMPTY"); }}
C#Main.cs · 70 줄
using System;using System.Collections.Generic;using System.Text;class Program{ // 편집 하나: 붙였는지(type) 지웠는지(erase)와 그 문자열 record Edit(bool Typed, string S); static readonly StringBuilder text = new StringBuilder(); static void Apply(Edit e) { if (e.Typed) text.Append(e.S); else text.Length -= e.S.Length; } static void Revert(Edit e) { if (e.Typed) text.Length -= e.S.Length; else text.Append(e.S); } static void Main() { int m = int.Parse(Console.ReadLine().Trim()); var undo = new Stack<Edit>(); // 되돌릴 수 있는 편집들 var redo = new Stack<Edit>(); // 되돌렸다가 다시 할 수 있는 편집들 for (int i = 0; i < m; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); switch (parts[0]) { case "type": { var e = new Edit(true, parts[1]); Apply(e); undo.Push(e); redo.Clear(); // 새 편집을 하면 다시 하기 목록은 사라진다 break; } case "erase": { int k = Math.Min(int.Parse(parts[1]), text.Length); if (k == 0) break; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) var e = new Edit(false, text.ToString(text.Length - k, k)); Apply(e); undo.Push(e); redo.Clear(); break; } case "undo": if (undo.TryPop(out var u)) { Revert(u); redo.Push(u); } break; case "redo": if (redo.TryPop(out var r)) { Apply(r); undo.Push(r); } break; } } Console.WriteLine(text.Length > 0 ? text.ToString() : "EMPTY"); }}
C++main.cpp · 64 줄
#include <algorithm>#include <iostream>#include <stack>#include <string>// 편집 하나: 붙였는지(type) 지웠는지(erase)와 그 문자열struct Edit { bool typed; std::string s;};std::string text;void apply(const Edit& e) { if (e.typed) text += e.s; else text.erase(text.size() - e.s.size());}void revert(const Edit& e) { if (e.typed) text.erase(text.size() - e.s.size()); else text += e.s;}int main() { int m; std::cin >> m; std::stack<Edit> undo; // 되돌릴 수 있는 편집들 std::stack<Edit> redo; // 되돌렸다가 다시 할 수 있는 편집들 for (int i = 0; i < m; i++) { std::string cmd; std::cin >> cmd; if (cmd == "type") { Edit e{true, ""}; std::cin >> e.s; apply(e); undo.push(e); redo = {}; // 새 편집을 하면 다시 하기 목록은 사라진다 } else if (cmd == "erase") { std::size_t k; std::cin >> k; k = std::min(k, text.size()); if (k == 0) continue; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) Edit e{false, text.substr(text.size() - k)}; apply(e); undo.push(e); redo = {}; } else if (cmd == "undo") { if (!undo.empty()) { Edit e = undo.top(); undo.pop(); revert(e); redo.push(e); } } else if (cmd == "redo") { if (!redo.empty()) { Edit e = redo.top(); redo.pop(); apply(e); undo.push(e); } } } std::cout << (text.empty() ? "EMPTY" : text) << "\n";}
Cmain.c · 82 줄
#include <stdio.h>#include <string.h>#define MAXM 10000#define MAXTEXT 50000/* 편집 하나: 붙였는지(type) 지웠는지(erase)와 그 문자열(많아야 100자) */typedef struct { int typed; int len; char s[101];} Edit;static char text[MAXTEXT + 1];static int textLen = 0;static Edit edits[MAXM]; /* 편집은 명령마다 많아야 하나 생긴다 */static int undoStack[MAXM], undoTop = 0; /* 되돌릴 수 있는 편집들(edits의 번호) */static int redoStack[MAXM], redoTop = 0; /* 되돌렸다가 다시 할 수 있는 편집들 */static void apply(const Edit *e) { if (e->typed) { memcpy(text + textLen, e->s, e->len); textLen += e->len; } else { textLen -= e->len; }}static void revert(const Edit *e) { if (e->typed) { textLen -= e->len; } else { memcpy(text + textLen, e->s, e->len); textLen += e->len; }}int main(void) { int m, count = 0; char cmd[16], arg[16]; scanf("%d", &m); for (int i = 0; i < m; i++) { scanf("%15s", cmd); if (strcmp(cmd, "type") == 0) { scanf("%15s", arg); Edit *e = &edits[count]; e->typed = 1; e->len = (int)strlen(arg); memcpy(e->s, arg, e->len); apply(e); undoStack[undoTop++] = count++; redoTop = 0; /* 새 편집을 하면 다시 하기 목록은 사라진다 */ } else if (strcmp(cmd, "erase") == 0) { int k; scanf("%d", &k); if (k > textLen) k = textLen; if (k == 0) continue; /* 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) */ Edit *e = &edits[count]; e->typed = 0; e->len = k; memcpy(e->s, text + textLen - k, k); apply(e); undoStack[undoTop++] = count++; redoTop = 0; } else if (strcmp(cmd, "undo") == 0) { if (undoTop > 0) { int id = undoStack[--undoTop]; revert(&edits[id]); redoStack[redoTop++] = id; } } else if (strcmp(cmd, "redo") == 0) { if (redoTop > 0) { int id = redoStack[--redoTop]; apply(&edits[id]); undoStack[undoTop++] = id; } } } text[textLen] = '\0'; puts(textLen > 0 ? text : "EMPTY"); return 0;}
Craykonmain.cray · 84 줄
// 편집 하나는 [종류, 문자열]: 종류는 "type"(붙임) 또는 "erase"(지움)text = "";undo = []; // 되돌릴 수 있는 편집들redo = []; // 되돌렸다가 다시 할 수 있는 편집들붙이기(s){ text = text + s;}끝지우기(개수){ text = text.부분문자열(0, text.길이 - 개수);}하기(edit){ 만약 (edit[0] == "type") { 붙이기(edit[1]); } 아니면 { 끝지우기(edit[1].길이); }}되돌리기(edit){ 만약 (edit[0] == "type") { 끝지우기(edit[1].길이); } 아니면 { 붙이기(edit[1]); }}m = 콘솔.줄읽기().공백제거().수로변환();반복 (i = 0; i < m; i++){ parts = 콘솔.줄읽기().공백제거().나누기(" "); cmd = parts[0]; 만약 (cmd == "type") { edit = ["type", parts[1]]; 하기(edit); undo.넣기(edit); redo.비우기(); // 새 편집을 하면 다시 하기 목록은 사라진다 } 아니면 만약 (cmd == "erase") { k = 수학.작은수(parts[1].수로변환(), text.길이); 만약 (k > 0) { edit = ["erase", text.부분문자열(text.길이 - k)]; 하기(edit); undo.넣기(edit); redo.비우기(); } } 아니면 만약 (cmd == "undo") { 만약 (undo.개수 > 0) { edit = undo[undo.개수 - 1]; undo.자리빼기(undo.개수 - 1); 되돌리기(edit); redo.넣기(edit); } } 아니면 만약 (cmd == "redo") { 만약 (redo.개수 > 0) { edit = redo[redo.개수 - 1]; redo.자리빼기(redo.개수 - 1); 하기(edit); undo.넣기(edit); } }}콘솔.쓰기(text.길이 > 0 ? text : "EMPTY");