[백준 / 실버2] 1406 에디터 (Java)

문제 보기

사용한 것

• add(), remove()를 O(1)로 수행하기 위한 야매 연결 리스트
  
  

풀이 방법

• LinkedList를 사용하기에는 포인터 개념이 없으므로 add(), remove()에 O(n)이 걸린다.
• 따라서 해당 구현체를 사용하면 시간 초과가 걸리므로, 야매 연결 리스트를 사용한다.
• 데이터를 담을 dat, 이전 주소(인덱스)를 저장할 pre, 다음 주소(인덱스)를 저장할 nxt를 충분한 크기로 할당한 후 각 배열의 0번째 인덱스를 더미로 만든다.
• unused로 다음번에 사용할 인덱스를 저장한다.
• 삽입, 삭제 과정을 반복하다보면 배열에 의미 없는 인덱스들이 많아져 메모리가 낭비되는데, 이 것이 코딩테스트에서만 사용되는 야매 연결 리스트 이름의 이유이다.

코드

public class Main {

    private static char[] dat = new char[1_000_000];
    private static int[] pre = new int[1_000_000];
    private static int[] nxt = new int[1_000_000];
    private static int unused = 1;

    public static void main(String[] args) throws IOException {
        dat[0] = '-';
        pre[0] = -1;
        nxt[0] = -1;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cursor = 0;
        String init = br.readLine();
        for (int i = 0; i < init.length(); i++) {
            add(cursor++, init.charAt(i));
        }

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

            switch (command[0].charAt(0)) {
                case 'L':
                    if (pre[cursor] != -1) {
                        cursor = pre[cursor];
                    }
                    break;
                case 'D':
                    if (nxt[cursor] != -1) {
                        cursor = nxt[cursor];
                    }
                    break;
                case 'B':
                    if (pre[cursor] != -1) {
                        remove(cursor);
                        cursor = pre[cursor];
                    }
                    break;
                default:
                    add(cursor, command[1].charAt(0));
                    cursor = nxt[cursor];
                    break;
            }
        }

        System.out.println(search());
    }

    private static String search() {
        StringBuilder sb = new StringBuilder();
        int addr = 0;
        while (nxt[addr] != -1) {
            sb.append(dat[nxt[addr]]);
            addr = nxt[addr];
        }
        return sb.toString();
    }

    private static void add(int addr, char ch) {
        dat[unused] = ch;
        pre[unused] = addr;
        nxt[unused] = nxt[addr];
        if (nxt[addr] != -1) {
            pre[nxt[addr]] = unused;
        }
        nxt[addr] = unused;
        unused++;
    }

    private static void remove(int addr) {
        nxt[pre[addr]] = nxt[addr];
        if (nxt[addr] != -1) {
            pre[nxt[addr]] = pre[addr];
        }
    }
}