[백준 1406 / Java / 실버2] 에디터

문제

 

문제 자체는 시뮬레이션인데, 시뮬레이션 그대로 구현하면 무조건 시간 초과가 난다. 시간제한이 0.3초고, 삽입/삭제를 직접 수행할 경우 명령어가 50만개라서 50만 * 10만 하면 500억번 연산이라 자료구조를 잘 활용해야 한다.

나는 ArrayDeque 2개를 활용했다.

 

import java.io.*;
import java.util.*;

public class 에디터_1406_v2 {

	static ArrayDeque<Character> left = new ArrayDeque<>();
	static ArrayDeque<Character> right = new ArrayDeque<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer commands;
		
		/** 초기 문자열 */
		String str = br.readLine();
		for (int i = 0; i < str.length(); i++) {
			left.add(str.charAt(i));
		}
		
		/** 모든 명령어 실행 */
		int M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			
			commands = new StringTokenizer(br.readLine());
			modifyStr(commands);
		}
		
		/** 결과 출력 */
		for (char c : left) {
			sb.append(c);
		}
		for (char c: right) {
			sb.append(c);
		}
		System.out.println(sb);
	}
	
	/** 명령어에 맞게 문자열을 수정하는 함수 */
	private static void modifyStr(StringTokenizer commands) {
		
		String cmd = commands.nextToken();
		
		// 문자를 커서 왼쪽에 추가
		if (cmd.equals("P")) {
			String value = commands.nextToken();
			left.add(value.charAt(0));
		}
		
		// 커서를 왼쪽으로 옮기기
		else if (cmd.equals("L")) {
			if (!left.isEmpty()) {
				right.addFirst(left.pollLast());
			}
		}
		
		// 커서를 오른쪽으로 옮기기
		else if (cmd.equals("D")) {
			if (!right.isEmpty()) {
				left.add(right.pollFirst());
			}
		}
		
		// 커서 왼쪽에 있는 문자 삭제
		else if (cmd.equals("B")) {
			if (!left.isEmpty()) {
				left.pollLast();
			}
		}
	}

}

 

개인적으로 이 방법이 가장 효율적인 방법이라 생각한다. 직관적이기도 하고.

 

left, right 스택을 나누어 저장하고, 커서를 옮기는 것을 left, right 요소를 옮기는 것으로 구현한다.

삭제할 때는 left의 tail 또는 right의 head를 지우면 되며, 삽입도 tail 이나 head에 하면 되므로,

삽입/삭제는 일반 배열에서 O(N) 이지만 이렇게 하면 O(1)에 수행된다.

 

import java.io.*;
import java.util.*;

public class 에디터_1406 {
	
	/** 연결리스트 사용 */
	static List<Character> list = new LinkedList<>();
	static ListIterator<Character> iter = list.listIterator();
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer commands;
		
		/** 문자열을 연결리스트에 할당 */
		String str = br.readLine();
		for (int i = 0; i < str.length(); i++) {
			iter.add(str.charAt(i));
		}
		
		/** 명령어 개수만큼 반복 */
		int M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			
			commands = new StringTokenizer(br.readLine());
			modifyStr(commands);
		}
		
		/** 결과 출력 */
		StringBuilder sb = new StringBuilder();
		for (char c : list) {
			sb.append(c);
		}
		
		System.out.println(sb);
	}
	
	/** 문자열을 조작하고 현재 커서를 반환하는 함수 */
	private static void modifyStr(StringTokenizer commands) {
		
		String cmd = commands.nextToken();
		
		// 커서 왼쪽에 삽입
		if (cmd.equals("P")) {
			String value = commands.nextToken();
			iter.add(value.charAt(0));
		}
		
		// 커서를 왼쪽으로 이동
		else if (cmd.equals("L")) {
			if (iter.hasPrevious()) {
				iter.previous();
			}
		}
		
		// 커서를 오른쪽으로 이동
		else if (cmd.equals("D")) {
			if (iter.hasNext()) {
				iter.next();
			}
		}
		
		// 커서 왼쪽 문자 삭제
		else if (cmd.equals("B")) {
			if (iter.hasPrevious()) {
				iter.previous();
				iter.remove();
			}
		}
	}
}

 

연결리스트와 ListIterator를 활용한 방법으로도 풀어보았다. 커서를 활용하는 이 에디터라는 문제와 완벽하게 호환되는 자료구조이다.

그러나 명령어를 숙지해야 하고 스택만큼 직관적이지가 않으며, 헷갈린다. 자주 사용되는 자료구조도 아니고.

 

그래서 처음엔 ListIterator 로 풀었다가, ArrayDeque를 활용한 스택 2개 방법으로 바꿔서 풀었다. 직관적이고 간단한 방법이 더 좋다고 생각한다.

 

결과

맨 아래꺼가 ListIterator, 맨 위에꺼가 ArrayDeque를 활용한 스택 2개 코드다. 미세하게 ListIterator가 더 빠르긴 한데, 빅오 표기법 기준으로 사실상 시간복잡도는 같고 더 직관적이니 스택 방식이 더 나은 것 같다.