해당 포스팅은 백준 1360번 되돌리기 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
문제
1. 문제 설명
두개의 명령만 지원하는 텍스트 에디터가 있다.
- “type c" : 현재 글의 가장 뒤에 문자 c를 추가한다.
- “undo t" : 이전 t초동안 수행된 작업을 역순으로 되돌린다.
처음 텍스트 에디터는 비어있다.
예를 들어, 다음과 같은 명령을 진행했다고 하자.
[예제 1]
1초 : type a
2초 : type b
3초 : type c
5초 : undo 3
3초가 끝날 때, 텍스트는 "abc"이다. 5초때, 이전 3초동안 한 작업을 역순으로 되돌려야 한다. c는 지워지고, b도 지워질 것이다. 따라서 a만 남는다.
[예제 2]
1초 : type a
2초 : type b
3초 : undo 2
4초 : undo 2
2초일 때, 텍스트는 “ab"이다. 3초때 모든 것이 되돌리기 되므로 텍스트는 빈 텍스트가 되고, 4초때 3초때 되돌리기 한 것이 되돌리기 되고, 2초때 type b한 것이 지워진다. 따라서 텍스트는 ”a"가 된다.
명령과 수행한 시간이 주어질 때, 마지막에 남은 텍스트를 구하는 프로그램을 작성하시오.
2. 입력
- [첫째 줄] : 명령 개수 N
- [2번째 줄 ~] : 명령, 수행시간
- 시간은 오름차순으로 주어진다.
- 명령 type c에서 c는 알파벳 숫자
- 명령 undo t에서 t는 1 이상 109 이하
- N은 50 이하 자연수
3. 출력
첫째 줄에 모든 명령을 수행한 후에 남아있는 텍스트를 출력한다.
풀이
1. 로직
이 문제는 각 명령에 대한 val과 시간을 메모이제이션하면 풀리는 문제이다. 되돌리기 작업을 되돌리기 할 수 있다는 것은 다시금 어떤 시간 때의 text로 돌아갈 수 있어야 하기 때문이다.
따라서 각 시간 때의 값을 저장할 수 있는 배열 arr를 만든 후, [각 명령이 들어왔을 때의 text, 시간] 배열을 push하자.
해당 로직을 각 명령어에 대해서 설명하면 아래와 같다.
- 명령어가
type일 때는 이전 text에 이번에 들어온 문자를 더한 후 메모이제이션한다. - 명령어가
undo일 때는 수행시간 - 되돌리는 시간 이전의 text를 메모이제이션한다.
모든 명령문을 loop돌았다면, arr의 마지막 원소의 첫 번째 원소가 최종 text가 된다. (각 el의 첫 번째 원소는 text, 두 번째 원소는 시간이다)
2. 예제
예제를 통해 해당 로직을 설명하겠다.
a. [예제 1]
예제 1을 표로 설명하면 아래와 같다.
| 명령 | type a 1 | type b 2 | type c 3 | undo 3 5 |
|---|---|---|---|---|
| idx | 0 | 1 | 2 | 3 |
| curr | [a, 1] | [ab, 2] | [abc, 3] | [a, 5] |
- curr에는 [현재 text, 시간]을 저장한다.
- type의 경우
이전 idx curr의 text + 이번의 문자를 text로 갖는다.- "type c 3" 명령일 때 이전 text는 "ab"이다.
- 따라서 3초일 때의 텍스트는
이전 text ab + 이번 문자 c를 더해 "abc"이다. - 배열에 [abc, 3]를 저장한다.
- undo의 경우
수행시간 - 되돌리는 시간이전의 text를 text로 갖는다,- "undo 3 5" 명령일 때 수행시간은 5, 되돌리는 시간은 3이다.
- 따라서 5-3, 즉 2초 이전의 text로 돌아가야 하므로 1초 때의 text인 "a"가 된다.
- 모든 명령어 loop를 마치게 되면 arr는
[[a, 1], [ab, 2], [abc, 3], [a, 5]]가 된다. 최종 text는 "a"이므로arr[arr.length - 1][0]을 출력한다.
b. [예제 2]
예제 2를 표로 설명하면 아래와 같다.
| 명령 | type a 1 | type b 2 | undo 2 3 | undo 2 4 |
|---|---|---|---|---|
| idx | 0 | 1 | 2 | 3 |
| curr | [a, 1] | [ab, 2] | ["", 3] | ["a", 4] |
-
1초일 때 "type a", 2초일 때 "type b" 명령어를 수행하므로, 2초일 때 text는 "ab"이다.
- 2초일 때 arr는 [[a, 1], [ab, 2]]이다.
-
3초일 때 "undo 2" 명령어를 수행한다. 3-2, 즉 1초 이전의 text로 돌아가는데, 1초 이전의 text가 없으므로 text는 빈 문자열이다.
- 3초일 때 arr는 [[a, 1], [ab, 2], ["", 3]]
-
4초 때 "undo 2" 명령어를 수행한다. text는 4-2, 2초 이전의 text로 돌아가므로 1초 때의 text인 "a"가 된다.
- 3초일 때 arr는 [[a, 1], [ab, 2], ["", 3], [a, 4]]
-
모든 명령어 loop를 마치게 되면 arr는 [[a, 1], [ab, 2], ["", 3], [a, 4]]가 된다. 최종 text는 "a"이므로 arr[arr.length - 1][0]을 출력한다.
전체 코드
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0, -1);
const n = +input.shift();
const parsed = input.map(el => el.split(" "));
const arr = [];
let prev;
let now;
for (let i = 0; i < n; i++) {
let [cmd, val, sec] = parsed[i];
val = (typeof val === 'number') ? Number(val) : val;
sec = Number(sec);
// type
if (cmd === 'type') {
prev = (arr[i-1]) ? arr[i-1][0] : "";
now = prev + val;
arr.push([now, sec]);
continue;
}
// undo
let undoSec = (sec - val - 1);
let flag = false;
for (let j = arr.length -1; j >= 0; j--) {
if (undoSec < 0) break;
if (arr[j][1] <= undoSec) {
flag = true;
arr.push([arr[j][0], sec]);
break;
}
}
if (!flag) {
now = "";
arr.push(["", sec]);
}
}
const result = arr[arr.length - 1][0] ?? "";
console.log(result);