링크
https://www.acmicpc.net/problem/1406
문제 설명
(정답률 26.574%)
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
| 명령어 | 설명 |
|---|---|
| L | 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) |
| D | 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) |
| B | 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임 |
| P $ | $라는 문자를 커서 왼쪽에 추가함 |
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
입력 예제
abcd
3
P x
L
P y
출력 예제
abcdyx
나의 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine(); //초기 문자열
int m = Integer.parseInt(br.readLine()); //명령어 개수
//문자열을 LinkedList로 변환
LinkedList<Character> list = new LinkedList<>();
for (char c : str.toCharArray()) {
list.add(c);
}
//list의 객체를 하나씩 가져오기 위한 ListIterator
//양방향 탐색을 하기 위해 Iterator이 아니라 ListIterator 사용
ListIterator<Character> iterator = list.listIterator();
while (iterator.hasNext()) {
iterator.next();
}
for (int i = 0; i < m; i++) {
char[] chars = br.readLine().toCharArray();
char order = chars[0];
//입력된 명령어에 따라 수행
switch (order) {
//커서 왼쪽으로 이동
case 'L': {
if (iterator.hasPrevious())
iterator.previous();
break;
}
//커서 오른쪽으로 이동
case 'D': {
if (iterator.hasNext())
iterator.next();
break;
}
//커서 왼쪽 문자 삭제
case 'B': {
if (iterator.hasPrevious()) {
iterator.previous();
iterator.remove();
}
break;
}
//커서 왼쪽에 문자 추가
case 'P': {
iterator.add(chars[2]);
}
}
}
while (iterator.hasPrevious()) {
iterator.previous();
}
while (iterator.hasNext()) {
bw.write(iterator.next());
}
bw.close();
}
}다른 사람의 풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine();
int M = Integer.parseInt(br.readLine());
Stack<String> leftSt = new Stack<String>();
Stack<String> rightSt = new Stack<String>();
//처음 커서는 문장의 맨 뒤에서 시작하기 때문에 왼쪽 스택에 초기 문자를 모두 넣어줌 (ex. abc|)
String[] arr = str.split("");
for (String s : arr) {
leftSt.push(s);
}
for (int i = 0; i < M; i++) {
String command = br.readLine();
char c = command.charAt(0);
switch(c) {
case 'L':
if(!leftSt.isEmpty())
rightSt.push(leftSt.pop());
break;
case 'D':
if(!rightSt.isEmpty())
leftSt.push(rightSt.pop());
break;
case 'B':
if(!leftSt.isEmpty()) {
leftSt.pop();
}
break;
case 'P':
char t = command.charAt(2);
leftSt.push(String.valueOf(t));
break;
default:
break;
}
}
//Stack은 LIFO 구조이기 때문에
//왼쪽 스택에 있는 데이터들을 모두 오른쪽으로 옮긴 뒤에 오른쪽에 있는 모든 내용을 출력한다.
while(!leftSt.isEmpty())
rightSt.push(leftSt.pop());
while(!rightSt.isEmpty())
bw.write(rightSt.pop());
bw.close();
}
}정리
구현 자체는 크게 어렵지 않았는데 시간복잡도에서 문제가 있었다..
괜히 정답률이 낮은게 아니였다.
처음에는 ArrayList로 커서의 값을 인덱스로 증감시키면서 리스트를 수정했는데
문자의 길이가 최대 600,000자까지 입력할 수 있어서
특정 인덱스에 원소를 추가하고 제거하는 add(), remove()메소드로는 O(n)가 되어
시간초과가 날수 밖에 없었다.
처음에는 단순히 LinkedList는 add와 remove의 시간복잡도가 O(1)라서 이걸 쓰면 되겠구나 했지만 결국 특정 인덱스를 찾는다면 탐색까지 해야하므로 O(n)이다.
이 문제는 3개월전에 파이썬으로 코테 연습을 하던 때에도 결국 못 풀어서 포기했던 문제인데
이번에는 결국 구글링을 하였다..
방법은 반복자를 이용하여 푸는 것이였다.
실제 커서의 느낌으로 반복자를 움직이며 커서의 앞뒤에 문자를 추가하고 삭제한다.
Iterator를 실제로 써본적은 처음인데 Java Collection 개념이 많이 모자람을 느끼게 되었다..
공부할게 너무 많다~
보통 많이 푼 방법은 스택을 2개 생성해서 커서 각각 앞뒤 역할로 하는 것이 였는데
개인적으로 Iterator 풀이가 더 직관적인거 같다.
