[백준] 1406번 : 에디터

문제

주어진 명령어에 맞게 텍스트를 수정하는 에디터를 구현하는 문제

 

접근 방식

임의 위치의 요소를 수정해야 하니 배열보다는 연결 리스트를 사용하는 것이 좋을 것 같다.

 

커서의 위치를 기록하여 데이터의 추가/삭제 명령어가 입력 되었을 때

해당 커서의 인덱스를 수정하도록 하면 될거 같다.

 

사실 스택으로도 풀 수 있는 문제지만 연결 리스트에 대해 학습 중이기 때문에

지금은 연결 리스트로 풀고 나중에 다시 스택으로 풀어보겠다.

 

풀이

우선 처음 답안을 제출하고 시간 초과로 실패한 코드를 살펴보겠다.

 

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

    String before = br.readLine();
    int m = Integer.parseInt(br.readLine());

    LinkedList<Character> list = new LinkedList<>();

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

    int cur = list.size();

    for (int i = 0; i < m; i++) {
        String[] command = br.readLine().split(" ");

        switch (command[0]) {
            case "P": {
                list.add(cur, command[1].charAt(0));
                cur++;
                break;
            }
            case "L": {
                if (cur > 0) {
                    cur--;
                }
                break;
            }
            case "D": {
                if (cur < list.size()) {
                    cur++;
                }
                break;
            }
            case "B": {
                if (cur != 0) {
                    list.remove(cur);
                    cur = cur > 0 ? cur++ : cur;
                }
                break;
            }
        }
    }

    for (Character c : list) {
        System.out.print(c);
    }
}

 

자료형도 캐릭터로 바꿔보고 다 해봤는데도 왜 시간 초과가 뜨는지 알 수가 없어서

바킹독 선생님의 설명을 다시 보니 중요한 실수를 하고 있단걸 깨달았다.

 

연결 리스트는 분명 임의 위치의 요소를 수정하는 것이 효율적인 자료구조지만

그건 해당 인덱스의 주소를 알고 있는 경우에만 시간 복잡도가 O(1)이라는 것이다.

 

수정하려는 인덱스의 주소를 모르고 있다면

연결 리스트는 항상 처음부터 특정 인덱스의 위치까지 조회하는 O(N)의

시간 복잡도를 가지고 있기 때문이다.

 

그러면 지금 발생한 시간 초과를 해결하기 위해서는

특정 인덱스의 주소를 알고 있으면 된다는 의미다.

 

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 before = br.readLine();
    int m = Integer.parseInt(br.readLine());

    LinkedList<Character> list = new LinkedList<>();
    ListIterator<Character> iterator = list.listIterator();

    for (char c : before.toCharArray()) {
        iterator.add(c);
    }

    for (int i = 0; i < m; i++) {
        String command = br.readLine();

        switch (command.charAt(0)) {
            case 'P': {
                iterator.add(command.charAt(2));
                break;
            }
            case 'L': {
                if (iterator.hasPrevious()) {
                    iterator.previous();
                }
                break;
            }
            case 'D': {
                if (iterator.hasNext()) {
                    iterator.next();
                }
                break;
            }
            case 'B': {
                if (iterator.hasPrevious()) {
                    iterator.previous();
                    iterator.remove();
                }
                break;
            }
        }
    }

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

    bw.flush();
    bw.close();
}

 

ListIterator를 사용하면 이러한 문제를 해결할 수 있다.

 

자바에서 제공해주는 리스트 컬렉션을 수정하고 반복할 때 효과적인 클래스로

next()와 previous() 메서드를 사용해 양방향 순회가 가능하다.

 

ListIterator를 사용하고도 시간 초과가 났는데

출력도 BufferedWriter를 사용해야 시간 초과가 발생하지 않는다.