문제
시간 제한 0.3초, 메모리 제한 512 MB
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D : 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B : 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $ : $라는 문자를 커서 왼쪽에 추가함
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
입력
첫째 줄은 편집기에 입력되어 있는 문자열 (길이는 100,000를 넘지 않음)
둘째 줄에는 명령어의 개수 M (1<=M<=500,000)
이후 M개의 줄에 걸쳐 명령어가 주어짐
출력
명령 수행 후 편집기에 입력외어 있는 문자열 출력
풀이
^가 커서로 보고, 예시를 통해 이해하자면
abcd^
L을 하면 abc^d가 되고
D를 하면 abcd^
B를 하면 abc^ (왼쪽에 있는 것을 삭제하되, 커서도 한 자리 줄어들어야 함)
P 를하면abc^ (커서도 한 자리 늘어나야 함)
이렇게 되는 것이다.
처음 StringBuilder에 문자열을 집어넣고, idx에 StringBuilder의 길이를 넣는다.
이후 M번동안 for문을 돌며
1. L
idx-1을 한 것이 0보다 클 때만 idx를 줄인다.
2. D
idx+1을 한 것이 length보다 작거나 같을 때만 idx를 늘린다.
3. B
커서 왼쪽에 있는 문자를 삭제하는 것이므로 --idx 자리의 문자를 삭제한다. (deleteCharAt)
4. P
idx의 위치에 insert 후, idx를 늘린다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
sb.append(br.readLine());
int M = Integer.parseInt(br.readLine());
int idx = sb.length();
for(int i = 0; i<M; i++) {
st = new StringTokenizer(br.readLine());
switch(st.nextToken()) {
case "L":
if(idx - 1 >= 0) {
idx--;
}
break;
case "D":
if(idx + 1 <= sb.length()) {
idx++;
}
break;
case "B":
if(idx > 0) {
sb.deleteCharAt(--idx);
}
break;
case "P":
sb.insert(idx, st.nextToken());
idx++;
break;
}
}
System.out.println(sb.toString());
}
}문제를 풀며
풀고 나서 다른 풀이를 찾아봤더니 보통은 ListIterator와 Stack을 많이 사용한 것 같다.. 사실 나도 위 코드를 짜면서 시간초과가 날지 안 날지 긴가민가 했었다 🥹
LinkedList를 사용하는 방법은 시간 초과가 난다고 한다.
LinkedList는 전 인덱스의 요소와, 다음 인덱스의 요소를 가지고 있어서 이전, 다음 요소를 통해 정보를 처리하는 데에는 용이하지만 삽입/삭제는 비효율적이다. (삽입/삭제 시 맨 앞~맨 끝에서 일일히 찾아봐야 하므로)
1⃣ Iterator를 상속한 인터페이스인 ListIterator를 사용하면 커서를 앞 뒤로 이동시킬 수 있었다.
ListIterator<Character> li = list.listIterator();을 통해서 선언할 수 있다.
.hasPrevious(), .hasNext()를 통해 다음 요소가 있는지 확인할 수 있다.
.previous(), .next()를 통해 이동, .add(), .remove()를 통해 추가 및 제거도 가능하다.
2⃣ 스택을 통한 구현법은 이러하다.
스택 두 개를 구현해놓고, 커서가 어디로 가느냐에 따라 각 스택에 character를 옮겨주는 것이다.
abc^ 일 때
스택 1에는 abc, 스택 2는 빈 칸으로 냅둔다.
ab^c로 커서를 왼쪽으로 하나 옮기면,
스택 1에는 ab, 스택 2에는 c를 넣어두면 된다.
B일 때는 스택 1에서 pop, P일 때는 스택 1에 push하면 된다.
그리고 보통 StringBuilder를 사용했을 때 시간 초과가 났다는 글이 많았는데.. delete()가 아닌 deleteCharAt()을 사용하여 시간 초과가 안 난 걸까? 기본적으로 .delete()와 .deleteCharAt() 둘의 차이가 클 것 같지는 않아, 완전한 정답은 아니고 뽀록으로 맞은 것 같다는 생각이 든다.. 😅