[알고리즘] 에디터 (백준 1406번)

 

1406번: 에디터

 자료구조를 적절히 사용해서 시간 효율성을 따지는 문제이다. 함부로 내장 라이브러리를 사용하게 된다면 O(NM) 시간이 걸리기에 무조건 시간초과가 발생한다.

 때문에 한 번에 명령에 O(1) 시간이 걸려야하므로 총 O(M) 시간에 문제를 해결해야 한다.

 

Solution

 기본적으로 ArrayList, LinkedList 등은 내부적으로 값을 삽입, 조회, 삭제 시 O(N)시간이 걸리기에 사용해선 안된다. 난 Stack 2개를 활용해서 커서를 기준으로 왼쪽 문자열 스택, 오른쪽 문자열 스택으로 나누어서 왼쪽으로 이동할 때마다 left 스택을 pop 해서 right 에 push, 오른쪽으로 이동할 땐 반대의 과정을 거쳤다.

 

 

---

import org.omg.PortableInterceptor.INACTIVE;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


	static void solution() throws  Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String str = br.readLine();

		int N = str.length();

		Stack<Character> left = new Stack<>();

		for(int i = 0;i < N;i++)
			left.push(str.charAt(i));

		Stack<Character> right = new Stack<>();

		int M = Integer.parseInt(br.readLine());

		for(int i = 0;i < M;i++)
		{
			StringTokenizer strtok = new StringTokenizer(br.readLine());

			char order = strtok.nextToken().charAt(0);

			if(order == 'L')
			{
				if(!left.isEmpty())
					right.push(left.pop());
			}
			else if(order == 'D')
			{
				if(!right.isEmpty())
					left.push(right.pop());
			}
			//커서 왼쪽 문자 삭제
			else if(order == 'B')
			{
				if(!left.isEmpty())
					left.pop();
			}
			//커서 왼쪽 문자 추가
			else
			{
				char c = strtok.nextToken().charAt(0);

				left.push(c);
			}
		}

		while(!left.isEmpty())
			right.push(left.pop());

		while(!right.isEmpty())
			bw.write(right.pop()+"");

		bw.close();
	}




	public static void main(String[] args) {

		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}


}