[백준] 1406. 에디터 (JAVA)

이번에 풀어 볼 문제는 <백준 1406번.  에디터>이다.

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

📌 문제 탐색하기

목표

모든 명령어를 수행하고 난 후, 편집기에 남아 있는 문자열 구하기

해야 할 것

1. 초기 문자열을 어떻게 저장해야할까?

2. 커서의 움직임은 어떤 방식으로 기록해야할까?

입력

[첫줄] 문자열 ( 길이 N ≤ 10^5 , 영어 소문자로만 이루어짐 )

[둘째 줄] M : 입력할 명령어의 개수 ( 1 ≤ M ≤ 500,000 )

[셋째 줄 ~ ] : 입력할 명령어 (L,D,B,P$ 중 하나)

 

아이디어

1. 초기 문자열을 어떻게 저장해야할까?

➡️문자열의 크기가 계속 변하니까 단순 배열이 아닌 동적 자료구조를 사용하는 것이 좋겠다.

➡️삽입, 삭제가 잦기 때문에 ArrayList 보다 LinkedList를 사용하는 것이 효율적일 것 같다.

 

 

2. 커서의 움직임은 어떤 방식으로 기록해야할까?

➡️커서는 항상 자신의 왼쪽 자리에 영향을 끼친다.

➡️자바에서는 컬렉션을 인덱스로 순회하면서 해당 컬랙션을 동시에 삭제하려고 하면 ConcurrentModificationException 예외를 발생시킨다. 따라서 Iterator, List 계열의 경우 ListIterator 를 사용하여 조작한다.

 ListIterator 관련 문법 정리

일단, ListIterator는 Iterator를 확장한 인터페이스로, 리스트(List)를 순회할 때 양방향 순회가 가능하도록 하고, 순회하면서 동시에 요소 추가, 삭제, 수정을 안정적으로 지원해주는 역할을 한다.

ListIterator는 커서(cursor)를 통해 요소를 순회하는데, 여기서 커서란 리스트 내에서 현재 위치를 가리키는 개념이다.

ListIterator를 생성하면 커서는 리스트의 가장 앞(0번 인덱스)에 위치한다.
+ 기본적으로 Iterator는 커서 위치를 명시적으로 지정할 수 없지만, ListIterator의 경우 커서의 시작 위치를 명시적으로 설정할 수 있도록 제공한다.

listIterator(int index) 
: index는 커서가 가리킬 시작 위치를 의미한다. 커서는 해당 index의 앞쪽(왼쪽)에 위치한다.
ex) listIterator(0) : 리스트의 시작, listIterator(list.size()) : 리스트의 끝

next()를 호출 시 현재 위치에서 오른쪽 요소를 반환하고, 커서를 오른쪽으로 한 칸 이동시킨다.
previous() 호출 시 현재 위치에서 왼쪽 요소를 반환하고, 커서를 왼쪽으로 한 칸 이동시킨다.
add() 현재 커서 위치에 새 요소를 삽입한다. 삽입된 요소는 새 커서의 왼쪽에 위치한다.
set() 마지막으로 반환된 요소를 새로운 값으로 수정한다. 반환된 요소가 있어야하므로 next()나 previous()를 호출한 후에만 유효하다.
remove() 마지막으로 반환된 요소를 삭제한다. 마찬가지로 이 메서드도 next()나 previous()를 호출한 후에만 유효하다.

📌 코드 설계하기

1. input 단어들을 받고, 문자열을 LinkedList 형태로 저장한다.

2. ListIterator를 생성하여 각 조건에 맞게 커서를 이동시키는 로직을 구현한다.

3. 전체 명령을 수행한 뒤, 결과 문자열을 출력한다.

 

📌 정답 코드

1 회차 ( 시간 초과 )

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 bf = new BufferedReader(new InputStreamReader(System.in));
        String word = bf.readLine();
        LinkedList<String> wordList = new LinkedList<>(
                Arrays.asList(word.split(""))
        );

        ListIterator<String> iterator = wordList.listIterator(wordList.size());

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

        for (int i=0; i<M; i++){
            String commend = bf.readLine();

            if (commend.equals("L")){
                if(iterator.hasPrevious()){
                    iterator.previous();
                }
            }else if (commend.equals("D")){
                if(iterator.hasNext()){
                    iterator.next();
                }
            }else if (commend.equals("B")){
                if(iterator.hasPrevious()){
                    iterator.previous();
                    iterator.remove();
                }
            }else{
                String[] str = commend.split(" ");
                String alphabet = str[1];

                iterator.add(alphabet);

            }
        }

        iterator = wordList.listIterator(0);
        while(iterator.hasNext()){
            System.out.print(iterator.next());
        }
        

    }
}

 

이 코드를 실행하니까 시간 초과가 떴다..  어떤 부분이 시간초과 되는 것인지 코드를 하나하나 뜯어보았다.

LinkedList<String> wordList = new LinkedList<>(
                Arrays.asList(word.split(""))
        );

➡️ String.split() 메서드는 입력된 문자열을 한 번 순회하면서 분리작업을 수행한다. 그러므로 문자열의 길이를 n이라고 할 때, 시간복잡도는 O(n) 이다.

➡️Arrays.asList() 는 배열을 기반으로 고정된 크기의 리스트를 생성한다. 리스트를 생성할 때 배열의 참조 주소를 복사하기만 하면 되기 때문에 시간 복잡도는 O(1)

➡️new LinkedList<>() 는 LinkedLit 생성자에 다른 컬렉션을 전달하고 있는 것이다. 그럼, 해당 컬렉션의 모든 요소를 순회하며 새 노드를 생성하고 링크드 리스트로 만든다. 따라서 입력 리스트의 길이가 n이라면, 리스트를 순회하면서 각 요소를 복사하기 때문에 O(n)의 시간복잡도를 가진다.

ListIterator<String> iterator = wordList.listIterator(wordList.size());

➡️ LinkedList는 리스트의 사이즈를 저장하고 있다. 그러므로 wordList.size() 는 O(1)로 바로 수행 가능하다.

➡️listIterator(int index)을 수행하기 위해 LinkedList는 앞에서부터 노드를 순차적으로 탐색한다. 전달된 index가 리스트의 크기 n과 가까운 경우는 리스트를 끝부터 탐색할 수 있게 구현되어 있긴 하지만 일단 이론적으로는 탐색하기 위해 최악의 경우 O(n)의 시간이 걸린다.

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

        for (int i=0; i<M; i++){
            String commend = bf.readLine();

            if (commend.equals("L")){
                if(iterator.hasPrevious()){
                    iterator.previous();
                }
            }else if (commend.equals("D")){
                if(iterator.hasNext()){
                    iterator.next();
                }
            }else if (commend.equals("B")){
                if(iterator.hasPrevious()){
                    iterator.previous();
                    iterator.remove();
                }
            }else{
                String[] str = commend.split(" ");
                String alphabet = str[1];

                iterator.add(alphabet);

            }
        }

➡️입력된 명령의 개수 M만큼 반복된다.

➡️각 명령어는 상수시간에 실행 가능하다.

iterator = wordList.listIterator(0);
        while(iterator.hasNext()){
            System.out.print(iterator.next());
        }

 ➡️ while 문에서 리스트의 크기( = 남은 문자열의 크기 )만큼 모든 요소를 순회하며 출력하므로 평균 O(n)의 시간 복잡도를 가진다.  하지만 만약 M번의 입력 명령이 P $ 라 글자가 추가되는 명령만 수행되었다면 최악의 경우 N+M 번의 연산을 수행해야한다. 

 

전체 시간 복잡도는 O(N + M + N+M) = O(2N + 2M) 으로 정리해 볼 수 있을 것 같다.

N의 최대값은 10^5, M의 최대값은 5*10^5 이므로 최악의 경우 1,200,000 번의 연산을 수행해야 한다. 

 

2회차 ( 출력 부분 변경 )

 

이 문제의 Java 제한시간은 2초이기 때문에 큰 문제가 될 것 같지 않은데..?알고보니 출력 방식의 문제였다.출력하는 방식을 StringBuilder 나 BufferedWriter 를 사용하는 방식으로 변경하였더니 통과되었다.

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (String s : wordList){
            bw.write(s);
        }

        bw.flush();

 

일반적으로 I/O 연산은 CPU보다 느리기 때문에 이렇게 많은 연산을 반복해서 처리하면 병목 현상을 일으킨다고 한다.

따라서 이런 경우 매번 System.out.println을 하는 것이 아니라 StringBuilder나 BufferedWriter를 사용해서 출력할 텍스트를 모았다가 한 번에 출력 시키면 출력 속도가 크게 향상된다.

📌 알게 된 것

많은 문자열을 출력할 때는 StringBuilder 나 BufferedWriter 사용하는 것 습관화하기!

 

그리고 문자 하나를 다룰 때는 입력값을 String으로 유지하는 것 보다 char로 사용하는 것이 효율적이라고 한다.

< 사용 가능한 문법 >
String.charAt(int index) : String의 특정 위치에 있는 문자를char로 반환한다.
String.toCharArray() : String을 char 배열로 반환한다. 이후, for-each 문으로 하나씩 꺼내오며 필요한 작업을 수행하는 식으로 진행하는 경우가 많다.
찾아보니, 이 문제는 스택을 이용해서도 풀 수 있었다.

커서가 가운데 있다고 생각하고, 커서의 왼쪽에 있는 문자들은 왼쪽 스택에, 커서의 오른쪽에 있는 문자들은 오른쪽 스택에 넣는다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String input = br.readLine();

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

        Stack<Character> leftStack = new Stack<>();
        Stack<Character> rightStack = new Stack<>();

        //처음 주어진 문자열은 모두 왼쪽 스택에 넣어 초기화
        for (char c : input.toCharArray()){
            leftStack.push(c);
        }

        for (int i = 0; i<N; i++){
            String command = br.readLine();
            processCommand(command, leftStack, rightStack);
        }

        while (!leftStack.isEmpty()){
            rightStack.push(leftStack.pop());
        } //마지막에 출력할 땐 왼쪽 스택에 모든 문자열을 몰아넣기
        while(!rightStack.isEmpty()){
            sb.append(rightStack.pop());
        }

        System.out.println(sb);
    }

    private static void processCommand(String command, Stack<Character> leftStack, Stack<Character> rightStack){
        char cmd = command.charAt(0);

        switch(cmd){
            case 'L':
                if (!leftStack.isEmpty()){
                    rightStack.push(leftStack.pop());
                }
                break;

            case 'D':
                if(!rightStack.isEmpty()){
                    leftStack.push(rightStack.pop());
                }
                break;

            case 'B':
                if (!leftStack.isEmpty()){
                    leftStack.pop();
                }
                break;

            case 'P':
                char x = command.charAt(2);
                leftStack.push(x);
                break;

        }

    }
}