[백준] 1406번 : 에디터 (JAVA)

인간몽쉘김통통·2023년 12월 17일

백준 스택 알고리즘 자료구조

백준

목록 보기

35/92

문제

이해

간단한 문자열 에디터를 구현해야 한다.

문자열을 조작하는 명령어는 현재 문자열 상에서 위치하는 커서를 기준으로 수행된다.

커서는 현재 문자열의 위치를 나타내며 이를 통해 삭제, 삽입을 수행한다.

구현해야 하는 명령어는 다음과 같다.

최초에 커서는 문자열의 가장 뒤쪽에 위치하고 있다.

초기 입력 문자열 길이는 100,000을 넘지 않고 명령어의 개수 M은 최대 500,000까지 입력가능하다.

최종적으로 에디터에 입력되어 있는 문자열을 출력하면 된다.

접근

풀이 1

처음에는 문제가 원하는 대로 단순하게 구현하였다.

말그대로 커서를 기준으로 문자열을 수정하면 되었기 때문에 String 클래스의 메소드를 이용하기로 했다. 수정은 String.substring을 이용했다.

    static void cmd_P(String input){
        s = s.substring(0, cursur) + input + s.substring(cursur, s.length());
        cursur++;
        return;
    }

위는 P 명령어를 수행하는 메소드이다. substring을 이용해서 커서 앞쪽의 문자열 + 삽입 문자 + 커서 뒤쪽의 문자열 을 수행하여 문자를 삽입한다.

하지만 위 방법은 시간초과가 발생했는데 이는 수행해야 하는 명령어가 최대 500,000개이기도 하면서 substring의 연산과정이 오래걸린 것이 원인으로 보인다.

따라서, String 클래스를 이용하지 않고 LinkedList를 이용해 보았다.

풀이 2

    static void cmd_B() {
        if (cursur == 0) {
            return;
        }
        s_link.remove(cursur - 1);
        cursur--;
        return;
    }

    static void cmd_P(String input) {
        s_link.add(cursur, input.charAt(0));
        cursur++;
        return;
    }

위는 LinkedList로 구현한 명령어 B, P의 메소드이다.

s_link는 문자열을 담은 LinkedList이다.

이전 풀이 방법의 substring 메소드의 시간복잡도를 정확하게 알지는 못하지만 LinkedList를 이요한 삽입, 삭제가 더 빠르다고 생각됐다.

그도 그럴게 LinkedList의 삽입, 삭제 과정은 연산이 이루어지는 위치 (커서 위치) 에서의 연결만 끊고 새로이 연결하기만 하면 되기 때문이다.

하지만 이 방법도 시간초과가 발생했다.

예상되는 원인으로는 LinkedList의 삽입, 삭제를 위해서는 LinkedList를 탐색해야 하는데 이 때 구조 특성상 무조건 순차적으로 탐색해야 하기 때문에 시간이 오래 걸린 것 같다.

( 시간복잡도는 O(n) 이다.)

따라서, 시간적으로 더 개선하기 위해 스택을 이용해 다음 풀이를 진행해보았다.

풀이 3

    static void cmd_B(){
        if(L_stack.isEmpty()){
            return;
        }
        L_stack.pop();
        return;
    }
    static void cmd_P(String input){
        L_stack.add(input.charAt(0));
        return;
    }

위는 스택을 이용한 명령어 B, P의 메소드이다.

이 풀이는 다른 사람의 풀이를 참고하여 작성되었다.

처음에 커서를 따로 설정하지 않고 스택을 두 개 생성한다.

각각 L_stack, R_stack이라 하자.

L_stack은 커서 이전의 문자열을 의미하고 R_stack은 커서 이후의 문자열을 의미한다.

따라서, 삭제 연산에서는 L_stack에서 pop을 수행하고, 삽입 연산에서는 L_stack에서 add만을 수행하면 된다.

이 방법이 문자열 삽입, 삭제할 때 시간적으로 가장 좋아보였다. 이미 커서의 위치를 알고 있기 때문에 탐색도 필요없으며 문자열을 자르는 과정도 필요없기 때문이다.

마지막으로 출력에 대한 부분도 역시 L_stack을 모두 pop하여 R_stack으로 옮기고 R_stack에서 차례로 pop하며 출력하면 된다.

이 과정은 위에서 설명했듯이 커서를 문자열의 맨 앞으로 옮기는 과정을 의미한다.

코드

package java_baekjoon;

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

public class prob1406_3 {
    static String s;
    static int M;
    static Stack<Character> L_stack;
    static Stack<Character> R_stack;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        L_stack = new Stack<>();
        R_stack = new Stack<>();

        s = br.readLine();
        for(int i=0;i<s.length();i++){
            L_stack.add(s.charAt(i));
        }

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

        while(M --> 0){
            StringTokenizer st = new StringTokenizer(br.readLine());

            String cmd = st.nextToken();

            if(cmd.equals("L")){
                cmd_L();
            }else if(cmd.equals("D")){
                cmd_D();
            }else if(cmd.equals("B")){
                cmd_B();
            }else if(cmd.equals("P")){
                String input = st.nextToken();
                cmd_P(input);
            }else{
                System.out.println("invalid cmd");
                return;
            }
        }

        while(!L_stack.isEmpty()){
            R_stack.add(L_stack.pop());
        }

        StringBuilder sb = new StringBuilder();
        
        while(!R_stack.isEmpty()){
            sb.append(R_stack.pop());
        }

        System.out.println(sb.toString());
    }    
    static void cmd_L(){
        if(L_stack.isEmpty()){
            return;
        }
        R_stack.add(L_stack.pop());
        return;
    }
    static void cmd_D(){
        if(R_stack.isEmpty()){
            return;
        }
        L_stack.add(R_stack.pop());
    }
    static void cmd_B(){
        if(L_stack.isEmpty()){
            return;
        }
        L_stack.pop();
        return;
    }
    static void cmd_P(String input){
        L_stack.add(input.charAt(0));
        return;
    }
}