1406번: 에디터(Java)

 처음에는 LinkedList로 간단하게 풀 수 있을 거라고 생각했다. 

BufferedReader와 LinkedList로 풀었는데 계속 시간 초과가 나왔다. 생각해 보니 시간복잡도가 O(n^2)이 나왔다. 시간복잡도를 O(n)으로 줄일 수 있는 방법이 무엇인지 고민하다가 Stack 두 개를 사용하면 삽입, 삭제를 O(1) 만에 할 수 있을 것 같아 Stack 두 개를 사용하기로 했다.

 

 

 

left, right 라는 Stack을 두 개 만들고 우선 left에 모든 문자를 넣은 후 커서를 left의 top으로 잡았다.

커서가 왼쪽으로 갈 때마다 right에 left.pop()을 push 하고 

커서가 오른쪽으로 갈 때는 left에 right.pop()을 push 하면 된다.

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Character> left = new Stack<>();
Stack<Character> right = new Stack<>();
String s = br.readLine();
for(int i = 0 ; i<s.length(); i++)
{
    left.push(s.charAt(i));
}

String[] command;
int n = Integer.parseInt(br.readLine());
for(int i = 0; i<n; i++)
{
    command = br.readLine().split(" ");

    switch (command[0])
    {
        case "L":
        {
            if(!left.isEmpty())
            {
                right.push(left.pop());
            }
            break;
        }
        case "D":
        {
            if(!right.isEmpty())
            {
                left.push(right.pop());
            }
            break;
        }
        case "B":
        {
            if(!left.isEmpty())
            {
                left.pop();
            }
            break;
        }
        case "P":
        {
            left.push(command[1].charAt(0));
            break;
        }
    }
}

 

 

여기까지는 문제 없는데 출력에서 문제가 발생했다. 

while(!left.isEmpty())
{
    right.push(left.pop());
}
while(!right.isEmpty())
{
    System.out.print(right.pop());
}

 

이런 방식으로 left에 있는 모든 원소를 right로 옮기고 System.out.print()로 출력했는데 시간 초과가 나왔다. 구글링을 좀 해 보니 System.out은 속도가 느리다는 사실을 알았다. 문제에서 명령어의 개수가 500,000이니 여러 번 출력해야 하므로 여기서 시간을 많이 잡아먹을 것 같았다. 그래서 StringBuilder를 사용해 한 번만 출력했다.

 

StringBuilder sb = new StringBuilder();
while(!left.isEmpty())
{
    right.push(left.pop());
}
while(!right.isEmpty())
{
    sb.append(right.pop());
}
System.out.println(sb);

 

 

 

<전체 코드>

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

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> left = new Stack<>();
        Stack<Character> right = new Stack<>();
        String s = br.readLine();
        for(int i = 0 ; i<s.length(); i++)
        {
            left.push(s.charAt(i));
        }

        String[] command;
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i<n; i++)
        {
            command = br.readLine().split(" ");

            switch (command[0])
            {
                case "L":
                {
                    if(!left.isEmpty())
                    {
                        right.push(left.pop());
                    }
                    break;
                }
                case "D":
                {
                    if(!right.isEmpty())
                    {
                        left.push(right.pop());
                    }
                    break;
                }
                case "B":
                {
                    if(!left.isEmpty())
                    {
                        left.pop();
                    }
                    break;
                }
                case "P":
                {
                    left.push(command[1].charAt(0));
                    break;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        while(!left.isEmpty())
        {
            right.push(left.pop());
        }
        while(!right.isEmpty())
        {
            sb.append(right.pop());
        }
        System.out.println(sb);
    }
}