[백준 - Java] 1406번 : 에디터

문제

https://www.acmicpc.net/problem/1406

 

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

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

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

 

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

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

입력

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

출력

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

 

 

1. LinkedList 사용해서 구현

순서도 있어야 하고 삽입, 삭제도 용이해야 하기 때문에 LinkedList를 이용하기로 했다.

 

LinkedList를 사용하기까지 공부한 것

[Java] Collection Framework - List / Set / Map

결과 - 시간 초과

2. 입출력 방식을 BufferedReader / BufferedWriter로 변경

LinkedList로 구현했던 첫번째 방식에서 Scanner로 입력을 받고 System.out.println("");으로 출력을 했다.

하지만 시간 초과가 나서 좀 더 빠르고 효율적인 입출력 처리를 위해 BufferedReader와 BufferedWriter를 사용했다.

 

BufferedReader / BufferedWriter

[Java] BufferedReader, BufferedWriter

1, 2 코드

import java.io.IOException;
import java.util.LinkedList;
import java.util.Scanner;
import java.io.*;

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<Character> list = new LinkedList<Character>();

		for(int i = 0; i < str.length(); i++) {
			list.add(str.charAt(i));
		}

		//index 변수를 이용해 cursor의 위치를 다루고자 함
		int index = list.size(); //처음 시작시 커서는 문장의 맨 뒤에서 시작해야함 (ex. abc|)

		for(int i = 0; i < M; i++) {
			String command = br.readLine();
			char c = command.charAt(0);
            
			switch(c) {
			case 'L':
				if(index != 0) {
					index = index - 1;
				}

				break;
			case 'D':
				if(index != list.size()) {
					index = index + 1;
				}

				break;
			case 'B':
				if(index != 0) {
					list.remove(index-1);
					index--;
				}
				break;
			case 'P':
				char t = command.charAt(2);
				list.add(index, t);
				index++;

				break;
			default:
				break;
			}
		}
		for(Character chr : list) {
			bw.write(chr);
		}
		
		bw.flush();
		bw.close(); 
	}
}

결과 - 시간 초과

LinkedList는 인접 참조를 링크해서 체인처럼 관리한다.

쉽게 말하자면 각 요소는 이전과 다음 요소의 정보를 가지고 있다.

그렇기에 ArrayList와 달리 임시 배열을 생성할 필요가 없고, 이전과 다음 요소의 정보를 활용하여 삽입/삭제를 처리할 수 있기에 유리하다.

그렇기 때문에 1과 2의 시도에서 LinkedList를 선택했다.

 

하지만 결국 이 문제는 삽입/삭제가 빈번한데 더 빠른 처리를 요구하고 있다.

즉 검색 시에는 인덱스를 통해 접근하는 것이 아니기에 최악의 경우는 모든 요소를 다 살펴봐야 하기 때문에 불리했다.

결국 ArrayList보다 유리하다고는 하나 결국 삽입/삭제 시 그 인덱스에 바로 접근하는 것이 아니라, head와 tail을 제외하곤 하나하나 살펴보며 찾아가서 처리하기 때문에 완전히 효율적이라고 볼 수 없다.

그래서 시간 초과가 났다고 생각한다.

 

즉 O(N)의 시간 복잡도를 가지게 되었고 커서 기준 거리 1 이내로 연산이 행해져야 하는 문제이기 때문에 모든 연산이 O(1)이여야 한다.

 

이 문제를 해결하기 위해 여러 질문들과 다른 사람들의 포스트를 찾아보았다. 

처음 구현한 방법에서는 index 변수를 이용해 커서의 위치를 다루었고, L/D/B/P 시 LinkedList가 커서의 위치, 즉 해당하는 인덱스를 찾고 삽입/삭제가 처리되는 방식이었다.

하지만 이처럼 위치를 찾아가지 말고 문제의 '커서'처럼 해당하는 위치에 계속 있으면서 삽입/삭제를 처리할 수 있게 하는 방법을 찾았다.

그 방법이 바로 ListIterator의 사용이다!

 

https://mygumi.tistory.com/62 [마이구미의 HelloWorld]

 

3. ListIterator 사용

ListIterator는 Iterator를 상속한 인터페이스다.

Iterator의 단방향 탐색과 달리 양방향 탐색이 가능하다.

그렇기에 이 문제처럼 양방향으로 이동하면서 수정하기에 효율적이다.

Iterator / ListIterator

[Java] Iterator / ListIterator

3 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;

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<Character> list = new LinkedList<Character>();

		for(int i = 0; i < str.length(); i++) {
			list.add(str.charAt(i));
		}

		//iterator 메소드 호출 
		ListIterator<Character> iter = list.listIterator();
		//처음 커서는 문장의 맨 뒤에 있어야하기 때문에 커서를 맨뒤로 이동시켜줌 (ex. abc|)
		while(iter.hasNext()) {
			iter.next();
		}
	
		for(int i = 0; i < M; i++) {
			String command = br.readLine();
			char c = command.charAt(0);
			switch(c) {
			case 'L':
				if(iter.hasPrevious())
					iter.previous();

				break;
			case 'D':
				if(iter.hasNext())
					iter.next();

				break;
			case 'B':
				//remove()는 next()나 previous()에 의해 반환된 가장 마지막 요소를 리스트에서 제거함
				if(iter.hasPrevious()) {
					iter.previous();
					iter.remove();
				}
				break;
			case 'P':
				char t = command.charAt(2);
				iter.add(t);

				break;
			default:
				break;
			}
		}
		for(Character chr : list) {
			bw.write(chr);
		}
		
		bw.flush();
		bw.close(); 
	}
}

결과 - 성공

4. Stack을 이용한 구현

LinkedList를 이용해 구현했지만 Stack을 이용한다면 초장부터 시간 초과의 늪에 빠지지 않을 수 있다.

 

스택은 모든 연산이 O(1)의 시간 복잡도를 가지기 때문에 시간 초과에 걸리지 않는다. (*시간 복잡도에 대한 내용 정리 필요)

커서의 왼쪽 오른쪽 구분을 위해 두 개의 스택을 사용한다.

예제 1의 경우

 

abcd
3
P x
L
P y

 

맨 처음 커서는 입력 문자열의 맨 뒤에 위치하기 때문에 문자열을 모두 왼쪽 스택에 넣어준다.

이후 차례로 명령어를 처리하면서 커서가 왼쪽으로 이동하면 왼쪽 스택의 가장 상단 요소를 오른쪽 스택에 pop() 시켜준다.

그리고 커서가 오른쪽으로 이동하면 오른쪽 스택의 가장 상단 요소를 왼쪽 스택에 pop() 시켜주며 마치 커서가 이동하는 것처럼 구현한다.

 

마지막 모든 명령어를 처리한 후에는 스택이 LIFO 구조이기 때문에 왼쪽 스택의 모든 요소들을 오른쪽 스택에 옮긴 후 오른쪽 스택을 모두 pop() 시키며 결과를 출력한다.

 

4 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main2 {

	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) { //Enhanced For Loop 사용 
			leftSt.push(s); 
		}
		
		for(int i = 0; i < M; i++) {
			String command = br.readLine();
			char c = command.charAt(0);
			//StringTokenizer st = new StringTokenizer(reader.readLine());
			//String c = st.nextToken();
			
			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));
				//leftSt.push(st.nextToken());

				break;
			default:
				break;
			}
		}
        
		//Stack은 LIFO 구조이기 때문에
		//왼쪽 스택에 있는 데이터들을 모두 오른쪽으로 옮긴 뒤에 오른쪽에 있는 모든 내용을 출력한다.
		while(!leftSt.isEmpty())
			rightSt.push(leftSt.pop());
		
		while(!rightSt.isEmpty())
			bw.write(rightSt.pop());
		
		bw.flush();
		bw.close(); 
	}
}

결과 - 성공

GITHUB

https://github.com/KwonMinha/BOJ/tree/master/BOJ%231406/src

KwonMinha/BOJ