백준 1406 풀이

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

처음 문제를 보았을 때는 단순하게 이 문제는 링크드리스트를 활용하여 입력받은 명령대로 처리하면 되는 간단한 문제인줄 알았다.

그래서 링크드리스트를 이용해 간단하게 코드를 작성했고 바로 채점을 해보았다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String txt = br.readLine();
        String n = br.readLine();
        int num = Integer.parseInt(n);

        int cur = txt.length();

        char[] tmp = txt.toCharArray();

        LinkedList<Character> list = new LinkedList<>();
        for(int i = 0;i<tmp.length;i++){
            list.add(tmp[i]);
        }

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

                cur = cur + 1;
            }
        }

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

위와 같은 코드로 채점을 했는데 '시간 초과'를 겪었다.

어디서 시간초과가 발생했는지 비슷한 상황을 겪고 있는 다른 사람들을 통해 힌트를 얻었는데 이 문제는 index를 통해 링크드리스트에 삭제할 값을 찾고 삽입하는 것은 O(n)이 걸리고 문제를 해결하기 위해서는 삽입, 삭제 둘 모두 O(1) 시간이 걸려야 한다는 것이다.

O(1)의 시간이 걸리기 위해서는 커서의 위치를 항상 기억하고 커서의 위치로 바로 접근할 수 있어야했다.
하지만 내가 아는 방법은 iterator뿐이고 iterator는 단방향으로만 진행이 가능했다.

그래서 구글에 iterator에 대해 알아보는 중 listiterator라는 확장된 iterator 클래스를 찾았고 양방향으로 진행이 가능하다는 것을 알았다.

https://minhamina.tistory.com/18

결국 listiterator를 활용해 문제를 풀었고 성공적이었다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String txt = br.readLine();
        String n = br.readLine();
        int num = Integer.parseInt(n);

        int cur = txt.length();

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

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

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

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

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