백준 1406 에디터 (JAVA 자바 풀이)

백준 1406 에디터 (JAVA 자바 풀이)

---

 

 

 

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

 

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

 

이 편집기가 지원하는 명령어는 다음과 같다.

 

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

 

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

 

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

 

---

 

 

💡 풀이 과정

 

시간 제한이 짧기 때문에 어떤 자료구조를 선택하는지가 중요할 것 같다. 

 

LinkedList는 중간 연산에 대해서 효율적인 성능을 보인다. 단, Iterator를 사용할 때만이다. 

 

패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online.

 

 

에디터 문제의 경우 명령어에 따라 문자열의 앞, 뒤, 좌우로 이동하여 수행하는 연산이 많으므로 iterator를 사용해서 풀어보면 좋을 것 같다. 

 

LinkedList에서 iterator가 가리키는 인덱스에 대한 삭제와 삽입 연산은 O(1)인데 왜 그럴까? 왜냐하면 연결 리스트에서 포인터가 가리키고 있는 바로 그것에 대한 연산이기 때문이다. 따라서 연산에 대한 시간 복잡도를 O(1)로 줄일 수 있으면 문제의 데이터인 50만 건에 대해 반복문을 돌릴 때 O(N) 즉, 최대 50만으로 풀이가 가능하다. 

 

시간 제한이 0.3초이기 때문에 타이트한 시간 제한을 맞출려면 연산 부분에서 상수 시간이 필요하다. 

 

알고리즘을 구현해보자. 

 

먼저 문자열을 받고 캐릭터 배열로 만들어둔다. 

 

StringTokenizer stringTokenizer = receiveInput(bufferedReader);
String string = stringTokenizer.nextToken();
List<Character> strings = new LinkedList<>();
for (char c : string.toCharArray()) {
   strings.add(c);
}

 

 

이제 명령어 개수를 받은 만큼 반복문을 돌리면서 커맨드를 받을 것인데, 모든 명령어를 미리 받아놓고 다시 재생하기 보다, 명령어를 받는 순간 처리를 해주도록 하자. 

 

그러기 위해 반복문에 앞서 iterator를 생성한다. 

 

ListIterator<Character> listIterator = strings.listIterator(strings.size());

 

이터레이터를 추가해준다. 이터레이터의 시작 위치는 처음 초기화하는 시점부터 맨 끝으로 위치된다. 

 

 

nextIndex가 4로 초기화되어 있는 것을 볼 수 있다.

 

 따라서 문제에 제시된 명령어들을 그대로 구현해주면 된다. 

 

// L -> 커서를 왼쪽으로. 맨 앞이면 무시
// D -> 커서를 오른쪽으로. 맨 뒤면 무시
// B -> 커서 왼쪽의 문자를 삭제. 맨 앞이면 무시
// P x -> 입력 받은 문자를 커서 왼쪽에 추가

 

 

이때 앞전으로 가는 메서드는 

listIterator.previous();

 

 

오른쪽으로 가는 메서드는 

listIterator.next();

 

더하는 메서드는 

listIterator.add(ch);

 

 

이다.

 

add의 경우 next 노드의 이전을 가리키고 있는 대상을 연결 시켜주는 방식으로 구현되므로 커서가 가리키는 뒤쪽에 추가가 된다. 

 

remove의 경우 연결 고리를 끊어버리면서 수행이 되는데, 방향키가 가장 최근에 리턴한 노드를 가리키고 있을 것이기 때문에 먼저 앞쪽으로 이동 후 뒷 글자를 삭제하는 형태로 적용해야 한다. 

 

listIterator.previous();
listIterator.remove();

 

 

예를 들어, d m i h 에서 B를 수행하는 경우를 살펴보자. 커서의 위치는 4를 가리키고 있다.  즉, d m i h <커서 위치>이다. 만약 이때 remove()를 수행하면 java.lang.IllegalStateException 이 발생하게 될 것이다. 삭제할 대상이 없기 때문이다. 따라서 그 앞쪽으로 이동하여 h를 가리키도록 하고, remove를 수행하면 d m i <커서 위치> h 인 상태에서 삭제가 수행되므로 원하는 h가 정상적으로 삭제된다. 

 

구현을 다 하고 나면 출력해주면 된다. 

 

StringBuilder answer = new StringBuilder();
for (char c : strings) {
   answer.append(c);
}
System.out.println(answer);

 

 

 

💡 코드 구현

 

 

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {

	private static StringTokenizer receiveInput(BufferedReader bufferedReader) throws IOException {
		return new StringTokenizer(bufferedReader.readLine());
	}

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));

		StringTokenizer stringTokenizer = receiveInput(bufferedReader);
		String string = stringTokenizer.nextToken();
		List<Character> strings = new LinkedList<>();
		for (char c : string.toCharArray()) {
			strings.add(c);
		}

		stringTokenizer = receiveInput(bufferedReader);
		int commandCounts = parseInt(stringTokenizer.nextToken());

		ListIterator<Character> listIterator = strings.listIterator(strings.size());

		// L -> 커서를 왼쪽으로. 맨 앞이면 무시
		// D -> 커서를 오른쪽으로. 맨 뒤면 무시
		// B -> 커서 왼쪽의 문자를 삭제. 맨 앞이면 무시
		// P x -> 입력 받은 문자를 커서 왼쪽에 추가
		for (int i = 0; i < commandCounts; i++) {
			stringTokenizer = receiveInput(bufferedReader);
			char cmd = stringTokenizer.nextToken().charAt(0);

			switch (cmd) {
				case 'L':
					if (listIterator.hasPrevious()) {
						listIterator.previous();
					}
					break;

				case 'D':
					if (listIterator.hasNext()) {
						listIterator.next();
					}
					break;

				case 'B':
					if (listIterator.hasPrevious()) {
						listIterator.previous();
						listIterator.remove();
					}
					break;

				case 'P':
					char ch = stringTokenizer.nextToken().charAt(0);
					listIterator.add(ch);
					break;
			}
		}

		StringBuilder answer = new StringBuilder();
		for (char c : strings) {
			answer.append(c);
		}
		System.out.println(answer);
	}

}