[BOJ 백준] 1406: 에디터 (자바 | Java)

[BOJ 백준] 1406: 에디터

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

---

1. 문제

• 시간 제한이 있다.
• LinkedList, ListIterator, BufferedReader, BufferedWriter를 이용해 풀이한다.
• LinkedList, ListIterator 개념, 메소드

---

2. PS

위 문제 해결을 위해 다음과 같이 문제를 쪼개어 생각 해봤다.
1. 문자열(str), 커서로 쓰일 문자열의 마지막 인덱스(n), 명령어 수(m)를 받는다.
2. 링크드리스트에 1에서 받은 문자열을 문자 하나씩 저장.
3. for문을 통해 m번 동안 명령어를 받는다.
4. for문을 한 번 돌 때마다 명령어(cmd)를 받고 명령어에 따른 if문을 통해 처리.
(이렇게 까지 하면 시간 초과가 발생 하였다.)
5. ListIterator 메소드 .next()로 커서를 이동하여 위치를 기억한다.

3. LinkedList 풀이 (시간 초과)

단순히 링크드리스트로 풀면 해결이 될 줄 알았다.
입력받은 명령 순서로 처리하고 바로 채점을 해보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String str = br.readLine();
        int n = str.length();
        int m = Integer.parseInt(br.readLine());
        LinkedList<Character> list = new LinkedList<Character>();

        for (int i = 0; i < n; i++) {
            list.add(str.charAt(i));
        }

        for (int i = 0; i < m; i++) {
            String cmd = br.readLine();
            if (cmd.charAt(0) == 'L') {
                if (n != 0) {
                    n -= 1;
                }
            } else if (cmd.charAt(0) == 'D') {
                if (n != list.size()) {
                    n += 1;
                }
            } else if (cmd.charAt(0) == 'B') {
                if (n != 0) {
                    list.remove(n-1);
                    n -= 1;
                }
            } else if (cmd.charAt(0) == 'P') {
                list.add(n, cmd.charAt(2));
                n += 1;
            }
        }

        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
        }

        System.out.println(sb);
    }
}

위 코드로 채점한 결과 시간초과가 나왔다.

3.1 시간초과가 나온 이유

위 코드에서 데이터의 삽입, 삭제를 하기 위해선 데이터의 인덱스 (코드에서는 n)에
접근하는데 드는 시간은 링크드리스트의 구조상 O(n)이 소요된다.
문제 해결을 위해선 O(1)의 시간이 필요하다. O(1)의 시간을 위해서는
커서의 위치를 기억하고, 삽입, 삭제시에 해당 커서에 바로 접근하여 작업을 해야한다.
방법을 찾던 도중 ListIterator에 대해 알게 되었고, 이를 사용하여 해결하였다.

4. LinkedLists, ListIterator 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;

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));
        String str = br.readLine();
        int n = str.length(); // 커서
        int m = Integer.parseInt(br.readLine());
        LinkedList<Character> list = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            list.add(str.charAt(i));
        }

        ListIterator<Character> iter = list.listIterator();
        while(iter.hasNext()) {
            iter.next();
        }

        for (int i = 0; i < m; i++) {
            String cmd = br.readLine();
            if (cmd.charAt(0) == 'L') {
                if (iter.hasPrevious()) {
                    iter.previous();
                }
            } else if (cmd.charAt(0) == 'D') {
                if (iter.hasNext()) {
                    iter.next();
                }
            } else if (cmd.charAt(0) == 'B') {
                if (iter.hasPrevious()) {
                    iter.previous();
                    iter.remove();
                }
            } else if (cmd.charAt(0) == 'P') {
               iter.add(cmd.charAt(2));
            }
        }

        for(Character c : list){
            bw.write(c);
        }
        br.close();
        bw.flush();
        bw.close();
    }
}