백준 1406번 에디터

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

1406번: 에디터

링크드리스트로 풀었다가 시간초과나서 덱2개 사용한풀이로 통과했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
		static List<Character> list = new LinkedList<>();
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			char [] word = br.readLine().toCharArray();
			int head = word.length;
			for(int i=0;i<head;i++) {
				list.add(word[i]);
			}
			int M = Integer.parseInt(br.readLine());
			for(int i=0;i<M;i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String token = st.nextToken();
				if(token.equals("L")) {
					if(head !=0) {
						head--;
					}
				}
				if(token.equals("D")) {
					if(head != list.size()) {
						head++;
					}
				}
				if(token.equals("B")) {
					if(head !=0) {
						list.remove(--head);
					}
				}
				if(token.equals("P")) {
					token = st.nextToken();
					list.add(head++, token.charAt(0));
				} 
			}
			StringBuffer sb = new StringBuffer();
			for(Character c : list) {
				sb.append(c);
			}
			System.out.println(sb);
		}
}

head 라는 변수를 두어서 커서위치를 기억하고 해당 커서 기준 앞뒤로 넣거나 빼는 알고리즘 풀이..(실패한것도 풀이라고 할수있나?)
링크드리스트는 탐색마다 n 만큼 시간복잡도가 드는데 그래서 시간초과가 났다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
		static ArrayDeque <Character> dq1 = new ArrayDeque<>();
		static ArrayDeque <Character> dq2 = new ArrayDeque<>();
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			char [] word = br.readLine().toCharArray();
			for(int i=0;i<word.length;i++) {
				dq1.addLast(word[i]);
			}
			int M = Integer.parseInt(br.readLine());
			for(int i=0;i<M;i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String token = st.nextToken();
				if(token.equals("L")) {
					if(!dq1.isEmpty()) {
						dq2.addFirst(dq1.pollLast());
					}
				}
				if(token.equals("D")) {
					if(!dq2.isEmpty()) {
						dq1.addLast(dq2.pollFirst());
					}
				}
				if(token.equals("B")) {
					if(!dq1.isEmpty()) {
						dq1.pollLast();
					}
				}
				if(token.equals("P")) {
					token = st.nextToken();
					dq1.addLast(token.charAt(0));
				} 
			}
			StringBuffer sb = new StringBuffer();
			for(Character c : dq1) {
				sb.append(c);
			}
			for(Character c : dq2) {
				sb.append(c);
			}
			System.out.println(sb);
		}
}

덱을 2개써서 커서 앞쪽이면 dq1에 뒤쪽이면 dq2에 처리하는 방식으로 풀었다. 큐나 스택으로 설계하다가 코드 갈아엎는 경우도 있는데.. 앞뒤로 다넣고 뺄 수 있으니 설계하기도 편하기도 하고. 앞 뒤에서 바로 넣고 빼니까 시간복잡도는 1