백준 1406번 : 에디터

문제

---

1406번: 에디터 (acmicpc.net)

1406번: 에디터

커서를 이용해서 문자열을 편집하는 문제

 

아이디어

---

🔸 첫번째 시도 : 커서와 문자열을 분리해서 해결. 문자열 편집에는 char[ ]을 이용.
      결과 : 시간 초과
      1. 하나의 명령어가 주어질 때 '커서를 계산하는 함수'와 '문자열을 계산하는 함수'를 호출하므로 함수 호출이 빈번
      2. char 배열을 이용했으므로 문자열을 편집할 때마다 새로운 길이의 배열을 만들고, → 매번 공간 복잡도 O(n)
         이전 배열을 복사하기 위해 for문과 assign 연산을 수행 → 매번 시간 복잡도 O(n)

🔸 두번째 시도 : 커서와 문자열 편집을 한번에 계산할 수 있게 해결. 함수 없앰. 문자열 편집에는 StringBuilder을 이용.
      결과 : 시간초과
      sb가 문자열 편집에 용이한 클래스이므로 코드는 훨씬 간결해졌지만,
      insert / delete 연산을 하기 위해 최악의 경우 O(n)의 시간 복잡도 발생

🔸 세번째 시도 : 두개의 Dequeue 이용하여, leftDQ에는 커서 왼쪽의 문자열, rightDQ에는 오른쪽 문자열이 오게 함
      결과 : 맞았습니다!
      삽입과 삭제에 O(1)가 걸리는 데크 이용.
      문자열 편집에는 char[ ]과 StringBuilder 뿐 아니라 스텍이나 큐도 사용될 수 있다는 것을 배움
      (커서에 의해서 큐 2개의 뒤와 앞이 연결된 구조)

package javaPractice.BJ1406ver3;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        LinkedList<String> leftDQ = new LinkedList<>(Arrays.asList(bf.readLine().split("")));
        LinkedList<String> rightDQ = new LinkedList<>();

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

        for (int i = 0; i < count; i++) {
            String command = bf.readLine();
            if("L".equals(command)){
                if(leftDQ.size()==0){ continue; }
                rightDQ.addFirst(leftDQ.pollLast());
            } else if("D".equals(command)){
                if(rightDQ.size()==0){ continue; }
                leftDQ.addLast(rightDQ.pollFirst());
            } else if("B".equals(command)){
                if(leftDQ.size()==0){ continue; }
                leftDQ.pollLast();
            } else if('P' == command.charAt(0)){
                leftDQ.addLast(String.valueOf(command.charAt(2)));
            }
            // System.out.print("leftST = " + leftDQ);
            // System.out.println("    rightST = " + rightDQ);
        }

        StringBuilder sb = new StringBuilder();
        while (leftDQ.size()>0) {
            sb.append(leftDQ.pollFirst());
        }
        while (rightDQ.size()>0) {
            sb.append(rightDQ.pollFirst());
        }
        bw.write(sb.toString());
        bw.flush();
    }
}

 

알게된 것

---

문자열을 편집하는 부분이 앞 or 뒤로 고정되어있다면, char[ ]이나 StringBuilder보다 스택이나 큐의 성능이 더 좋다.
함수 호출을 너무 많이 하면 시간초과 문제가 발생할 수 있다.
StringBuilder을 이용한 insert, remove를 연습할 수 있었다.