문제
초기 문자열과 편집 명령어가 주어진다. 커서를 기준으로 L(왼쪽 이동), D(오른쪽 이동), B(왼쪽 삭제), P x(왼쪽에 삽입) 명령을 수행한 결과를 출력하라.
입력
첫째 줄에 초기 문자열, 둘째 줄에 명령어 수 M, 이후 M개의 명령이 주어진다.
출력
모든 명령 수행 후 편집기에 남은 문자열을 출력한다.
예제
| 입력 | 출력 |
|---|---|
abcd 3 P x L B | abxd |
풀이
두 개의 스택으로 커서를 기준으로 좌우를 분리하여 모든 연산을 O(1)에 처리한다.
- 초기 문자열을 왼쪽 스택(stackL)에 모두 넣는다 (커서는 맨 끝)
- L: stackL에서 pop하여 stackR에 push (커서 왼쪽 이동)
- D: stackR에서 pop하여 stackL에 push (커서 오른쪽 이동)
- B: stackL에서 pop (커서 왼쪽 문자 삭제)
- P x: stackL에 x를 push (커서 왼쪽에 삽입)
- stackL을 모두 stackR로 옮긴 뒤 stackR을 순서대로 출력한다
핵심 아이디어: 커서 왼쪽/오른쪽을 각각 스택으로 관리하면 모든 편집 연산이 O(1)이다. 연결 리스트 대신 스택 2개로 구현하는 전형적 패턴이다.
코드
import java.io.*;
import java.util.*;
public class Day364BOJ1406에디터 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String s = br.readLine();
int m = Integer.parseInt(br.readLine());
Stack<Character> stackL = new Stack<>();
Stack<Character> stackR = new Stack<>();
for (int i = 0; i < s.length(); i++) {
stackL.push(s.charAt(i));
}
for (int i = 0; i < m; i++) {
String command = br.readLine();
char c = command.charAt(0);
if (c == 'L') {
if (stackL.size() != 0) {
stackR.push(stackL.pop());
}
}
else if (c == 'D') {
if (stackR.size() != 0) {
stackL.push(stackR.pop());
}
} else if (c == 'B') {
if (stackL.size() != 0) {
stackL.pop();
}
} else if ((c == 'P')) {
char t = command.charAt(2);
stackL.push(t);
}
}
while (stackL.size() != 0) {
stackR.push(stackL.pop());
}
while (stackR.size() != 0) {
bw.write(stackR.pop());
}
bw.flush();
bw.close();
}
}복잡도
- 시간: O(N + M) - 초기 문자열 길이 N + 명령어 수 M
- 공간: O(N + M)