[Java] 백준 1406번: 에디터

[문제 바로 가기] - 에디터

💡 접근 방식

문제에서 보다시피 시간 제한이 0.3초로 정말 짧다.
근데 나는 하단의 Java 8은 2초라고 되어있어 2초면 거뜬하지 않을까 싶었는데 아니었나 보다..
아무튼 처음엔 문제 유형을 보지 않고 풀어서 구현인줄 알았다.

1. substring 사용 => 시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int M = Integer.parseInt(br.readLine());
		
		int index = str.length();
		
		for (int i = 0; i < M; i++) {
			String command = br.readLine();
			String c = command.charAt(0) + "";
			if (c.equals("L") && index > 0) index--;
			else if (c.equals("D") && index < str.length()) index++;
			else if (c.equals("B") && index > 0) {
				str = str.substring(0, index - 1) + str.substring(index);
				index--;
			}
			else if (c.equals("P")) {
				if (index == 0) str = command.charAt(2) + str.substring(0);
				else str = str.substring(0, index) + command.charAt(2) + str.substring(index);
				index++;
			}
		}
		
		System.out.println(str);
	}
}

이클립스에서는 답이 잘 나와서 맞겠거니 했는데 시간초과가 떴다.
String 객체는 불변 객체이기 때문에 substring()을 사용해서 새로운 문자열을 만들어야 하기 때문에 O(n)의 시간 복잡도가 발생한다고 한다.
따라서 M개의 명령어마다 이것을 반복하므로 최종적으로 O(M*n)의 시간복잡도가 발생한다.

2. Stack 사용

문제 유형에 Stack이라고 적혀 있었는데 도저히 Stack으로는 어떻게 풀어야할지 모르겠어서 다른 사람의 풀이를 참고했다. (https://minhamina.tistory.com/17)
Stack을 2개 사용해서 명령어에 따라 Stack1과 Stack2에 각각 push하고 pop해준다.

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

/**
 * 백준 1406번 에디터
 * - Stack 사용
 */
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int M = Integer.parseInt(br.readLine());
		
		Stack<String> stack1 = new Stack<>();
		Stack<String> stack2 = new Stack<>();
		
		for (String s : str.split("")) {
			stack1.push(s);
		}
		
		for (int i = 0; i < M; i++) {
			String command = br.readLine();
			String c = command.charAt(0) + "";
		if (c.equals("L") && !stack1.isEmpty()) {
				stack2.push(stack1.pop());
			} else if (c.equals("D") && !stack2.isEmpty()) {
				stack1.push(stack2.pop());
			} else if (c.equals("B") && !stack1.isEmpty()) {
				stack1.pop();
			} else if (c.equals("P")){
				stack1.push(command.charAt(2) + "");
			}
		}
		
		while (!stack1.isEmpty()) {
			stack2.push(stack1.pop());
		}
		
		while (!stack2.isEmpty()) {
			System.out.print(stack2.pop());
		}
	}
}

하지만 이 코드도 시간초과가 떴다.. WHY?
설마 이건가 싶어서 System.out.print() 대신 StringBuilder를 사용했다.
그리고 command와 c도 for문 밖에서 미리 선언해주어서 매번 객체를 새로 생성하지 않도록 했다.

* 최종 코드

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

/**
 * 백준 1406번 에디터
 * - Stack 사용
 */
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String str = br.readLine();
		int M = Integer.parseInt(br.readLine());
		
		Stack<String> stack1 = new Stack<>();
		Stack<String> stack2 = new Stack<>();
		
		for (String s : str.split("")) {
			stack1.push(s);
		}
		
		String command;
		char c;
		
		for (int i = 0; i < M; i++) {
			command = br.readLine();
			c = command.charAt(0);
			if (c == 'L' && !stack1.isEmpty()) {
				stack2.push(stack1.pop());
			} else if (c == 'D' && !stack2.isEmpty()) {
				stack1.push(stack2.pop());
			} else if (c == 'B' && !stack1.isEmpty()) {
				stack1.pop();
			} else if (c == 'P'){
				stack1.push(command.charAt(2) + "");
			}
		}
		
		while (!stack1.isEmpty()) {
			stack2.push(stack1.pop());
		}
		
		while (!stack2.isEmpty()) {
			sb.append(stack2.pop());
		}
		
		System.out.println(sb);
	}
}

결국 통과!