백준 1406

▶ 1406문제 - 에디터

 

▶ 풀이방법

- LinkedList사용(시간초과 오류 발생)

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String str = br.readLine();
		int count = Integer.parseInt(br.readLine());
		LinkedList<Character> list = new LinkedList<>();
		for(int i = 0; i < str.length(); i++) {
			list.add(str.charAt(i));
		}
		
		int index = list.size();
		for(int i = 0; i < count; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			switch (st.nextToken()) {
			case "L":
				if(index != 0) index--;
				break;
			case "D" :
				if(index != list.size()) index++;
				break;
			case "B" :
				if(index != 0) {
					list.remove(index-1);
					index--;
				}
				break;
			case "P" :
				list.add(index, st.nextToken().charAt(0));
				index++;
				break;
			}
		}
		
		for(char c: list) {
			bw.write(c);
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

 

- Stack사용

import java.io.*;
import java.util.*;
public class Main {
	static String str;
	static int count;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Stack<Character> stack = new Stack<>();
		Stack<Character> stack2 = new Stack<>();
		
		str = br.readLine();
		count = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < str.length(); i++) {
			stack.push(str.charAt(i));
		}
		
		for(int i = 0; i < count; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			switch (st.nextToken()) {
			case "L":
				if(!stack.isEmpty()) stack2.push(stack.pop());
				break;
			case "D" :
				if(!stack2.isEmpty()) stack.push(stack2.pop());
				break;
			case "B" :
				if(!stack.isEmpty()) stack.pop();
				break;
			case "P" :
				stack.push(st.nextToken().charAt(0));
				break;
			}
		}
		
		while(!stack.isEmpty()) {
			stack2.push(stack.pop());
		}
		
		while(!stack2.isEmpty()) {
			bw.write(stack2.pop());
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

 

★알아둬야 할 것★

- LinkedList는 head랑 tail노드를 사용해 양쪽에서 삽입/삭제/접근/탐색을 하기 때문에 최대 시간복잡도가 O(n+1).

- stack이나 큐는 삭제/삽입할때 한쪽으로만 삽입/삭제 하니까 항상 시간복잡도가 O(1)이라 시간초과문제를 해결할 수 있다!