[BOJ][C++][Python] 백준 1406번 에디터
Updated:
1406번 에디터
1. 문제 정보
백준 온라인 저지 [1406번 에디터] 문제의 링크입니다.
문제
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다.
즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D : 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B : 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $ : $라는 문자를 커서 왼쪽에 추가함
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
입력
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.
출력
첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.
예제 입력1
abcd
3
P x
L
P y
예제 출력1
abcdyx
예제 입력2
abc
9
L
L
L
L
L
P x
L
B
P y
예제 출력2
yxabc
예제 입력3
dmih
11
B
B
P x
L
B
B
B
P y
D
D
P z
예제 출력3
yxz
시간 / 메모리 제한
0.3초 / 512MB
2. 생각
-
처음에는 배열을 이용하여 인덱스를 조정하며 커서를 옮기며 에디터의 기능을 구현하려고 했습니다. 배열 인덱스를 통해 임의의 위치를 접근할 수 있습니다.
-
그런데 이 에디터의 기능은 임의로 n번째의 위치에 접근하는 것이 아니고 왼쪽으로 한 칸(L), 오른쪽으로 한 칸(D), 왼쪽의 있는 문자 한 자 삭제(B), 왼쪽에 문자를 추가(P)하는 것 뿐입니다. 배열을 사용하면서 가장 문제되는 것이 문자를 삭제한 뒤에 어떻게 재 배열을 할 것인지의 문제가 있습니다. 아마 시간이 많이 걸리게 될 것입니다.
-
따라서 자료구조를 스택을 사용하겠습니다. 왼쪽 문자들을 담은 left 스택, 오른쪽의 문자를 담은 right 스택입니다. left는 앞의 문자부터 차례로 들어가고 right는 뒤의 문자부터 차례로 담길 것입니다. 여기서, 스택의 밖이 커서로 생각합니다.
-
L은 커서를 왼쪽으로 한 칸 옮기는 것이기 때문에 왼쪽 스택에서 오른쪽 스택으로 한 글자 옮깁니다.
D는 커서를 오른쪽으로 한 칸 옮기는 것이기 때문에 오른쪽 스택에서 왼쪽 스택으로 한 글자 옮깁니다.
B는 왼쪽 스택에 있는 가장 위의 문자 한 글자를 삭제합니다.
P는 $라는 글자를 왼쪽 스택에 삽입합니다.
3. 소스코드 (C++)
4. 소스코드 (Python)
