에디터 1406 JAVA

이번 문제는 스택에 대한 구조를 알고 있다면, 정말 쉽게 해결할 수 있었다.

 

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

 

이 문제를 구현하기 전, 우리가 고려해야 할 사항이 있다.

 

그것은 0.3초 내에 600,000개의 문자열을 처리해야 한다는 것이다.

만약 이를 구현할 때, 문자열을 하나 하나 다 뒤집어 가면서 구현하면 시간 복잡도는 O(M^2)라고 봐야한다.

정확히는 O(MN)이겠지만, 가장 앞에 있는 문자를 삭제하거나 추가할 땐, O(M^2)라고 봐도 상관이 없다.

 

그렇게 된다면 3600억이 되는데, 1억이 1초라고 그냥 가정하게 된다면 너무 많은 시간이 걸리기에 이렇게 구현하면 안된다.

 

이를 구현하기 위해선, 적어도 반드시 O(M)의 시간 복잡도를 가지는 코드여야 한다.

 

그럼 어떻게 구현할 수 있을까?

 

바로 커서 기준 왼쪽 문자열과 오른쪽 문자열을 구분하여 각각 스택에 담는 것이다.

예를 들어, ab|cd의 문자열일 때, ab는 왼쪽 스택에 cd는 오른쪽 스택에 담으면 된다.

 

조금 더 자세하게 얘기를 하자면, B는 왼쪽 스택의 top을 삭제하고, P는 새 문자를 push()하면 된다는 얘기다.

*당연히 문자가 없는 경우 삭제하려고 하면 안된다.

코드를 보면서 이해하면 쉽다.

 

case 'B':
    if(!leftStack.empty())
        leftStack.pop(); break;
case 'P':
    leftStack.push(input.charAt(2)); break;

이와 같이하면, 문자의 끝에서 커서의 위치까지 이동하면서 순회하지 않아도 단순하게 구현할 수 있게 된다.

 

마찬가지로 커서를 움직일 때도 단지 커서를 왼쪽으로 움직이면 왼쪽에서 빼서 오른쪽에 담고

오른쪽으로 움직이면 오른쪽에서 빼서 왼쪽에 담으면 된다. 

 

import java.io.*;
import java.util.Stack;

public class S1406 {
    static Stack<Character> leftStack = new Stack<>();
    static Stack<Character> rightStack = new Stack<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb  = new StringBuilder();

        for(char ch : br.readLine().toCharArray())
            leftStack.push(ch);

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

        while(N --> 0) {
            String input = br.readLine();
            char command = input.charAt(0);

            switch(command) {
                case 'L':
                    if(!leftStack.empty())
                        rightStack.push(leftStack.pop()); break;
                case 'D':
                    if(!rightStack.empty())
                        leftStack.push(rightStack.pop()); break;
                case 'B':
                    if(!leftStack.empty())
                        leftStack.pop(); break;
                case 'P':
                    leftStack.push(input.charAt(2)); break;
            }
        }

        leftStack.forEach(i -> sb.append(i));

        while(!rightStack.empty())
            sb.append(rightStack.pop());


        System.out.println(sb);
    }
}

 

마지막으로 나는 왼쪽 스택은 람다식을 이용하여 요소들을 저장하고, 오른쪽 스택도 이와 같이 빼서 출력하면 끝이다.