JAVA)1406번 stack을 사용하여 editor 만들기, 문자열의 + 연산과 StringBuilder와의 시간 소모 차이

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

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 sentence = br.readLine();
        for (int i=0;i<sentence.length();i++) {
            left.push(sentence.charAt(i)); // 문장의 끝으로 포인터 설정
        }
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String Command = br.readLine();
            switch (Command) {
                case "L" :
                    if (!left.empty()) {
                        char temp = left.pop();
                        right.push(temp);
                    }
                    break;
                case "D" :
                    if (!right.empty()) {
                        char temp = right.pop();
                        left.push(temp);
                    }
                    break;
                case "B" :
                    if (!left.empty()) {
                        left.pop();
                    }
                    break;
                default :
                    char word = Command.charAt(2);
                    left.push(word);
                    break;
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!left.empty()) {
            right.push(left.pop());
        }
        while (!right.empty()) {
            sb.append(right.pop());
        }
        System.out.println(sb);
        br.close();
    }
}

 

Cursor의 왼쪽 캐릭터들과 오른쪽 캐릭터들을 각 각 별도의 stack에 저장하여 editor를 구현하였다.

이번 문제의 핵심은 시간복잡도라고 할 수 있다.

문제에서 요구하는 기능은 스택을 사용하지 않고도 구현할 수 있다. 그러나 String만으로 editor기능을 구현할 경우 소요되는 시간이 너무 많게 된다. 

스택을 사용한다면 editor의 L, D, B, P의 각 기능을 O(1) 시간에 처리할 수 있다.

또한 editor를 통한 편집 이후 결과 출력에 있어서도 시간 소요를 줄이기 위해 StringBuilder를 사용하는 것이 좋다.

 

단순히 문자열의 + 연산만을 사용하여 결과를 만들어 낸다면, 스택으로 editor의 기능을 구현했다고 하더라도 시간 초과 판정을 받게 된다.

String은 내부적으로 Char[] 배열을 사용하는데 이 연산은 시간 소모가 크며, 대체할 방법이 구현되어 있지 않다.

이에 따라 StringBuilder를 사용하여 출력 결과를 구성하면 시간을 획기적으로 줄일 수 있다.

 

처음 문자열(문자열의 길이 = N)을 받아오고 커서의 위치를 설정하는데 O(N)의 시간이 걸린다.

각 editor의 연산들은 O(1)의 시간을 소모하며, 총 M개의 연산들이 수행되므로 전체 연산에 O(M)의 시간이 걸린다.

결과적으로 총 시간복잡도는 O(N + M)이다.

 

아래 코드는 스택을 사용하지 않고 문자열의 연산만으로 처리한 코드인다.

해당 코드는 시간 초과 판정을 받는 것을 확인할 수 있다.

String 클래스의 substring 메소드와 문자열 간의 + 연산이 소모하는 시간이 크기 때문에 빠른 코드를 만들고 싶다면 이들의 사용을 피하는 것이 바람직하다.

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

public class Main {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int cursor = 0;
        String sentence = br.readLine();
        cursor = sentence.length();
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String Command = br.readLine();
            switch (Command) {
                case "L" :
                    if (0 < cursor) {
                        cursor--;
                    }
                    break;
                case "D" :
                    if (cursor < sentence.length()) {
                        cursor++;
                    }
                    break;
                case "B" :
                    if (0 < cursor) {
                        String temp1 = sentence.substring(0, cursor-1);
                        String temp2 = sentence.substring(cursor);
                        sentence = temp1 + temp2;
                        cursor--;
                    }
                    break;
                default :
                    String word = Command.substring(2);
                    String temp1 = sentence.substring(0, cursor);
                    String temp2 = sentence.substring(cursor);
                    sentence = temp1 + word + temp2;
                    cursor++;
                    break;
            }
        }
        bw.write(sentence);
        bw.flush();
        br.close();
        bw.close();
    }
}

 

cf) 해당 문제는 LinkedList를 활용해서도 풀 수 있다고 한다.