문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    char[] input = br.readLine().toCharArray();

    LinkedList<Character> list = new LinkedList<>();
    for (char c : input) {
        list.add(c);
    }

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

    int n = Integer.parseInt(br.readLine());

    while (n-- > 0) {
        String command = br.readLine();

        switch (command) {
            case "L" :
                if (it.hasPrevious()) {
                    it.previous();
                }
                break;
            case "D" :
                if (it.hasNext()) {
                    it.next();
                }
                break;
            case "B" :
                if (it.hasPrevious() && !list.isEmpty()) {
                    it.previous();
                    it.remove();
                }
                break;
            default:
                it.add(command.charAt(2));
                break;
        }
    }

    StringBuilder sb = new StringBuilder();
    for (char c : list) {
        sb.append(c);
    }

    System.out.println(sb);
}
  • 이 문제는 로직보다 걸리는 시간이 문제였다.
  • 처음엔 LinkedList를 그대로 사용해 add, remove를 했지만 시간초과로 인해 ListIterator을 이용해 해결했다.

ListIterator

  • List를 양방향으로 탐색하고, 루프 중에 리스트를 수정하고, 리스트에서 현재 위치를 가져올 수 있다.
  • 커서는 previous()로 리턴되는 원소와 next()로 리턴되는 원소 사이에 존재한다.
1
2
                    Element(0)   Element(1)   Element(2)   ... Element(n-1)
cursor positions:  ^            ^            ^            ^                  ^
  • remove()와 set()를 호출해도 커서의 위치는 움직이지 않는다.
  • remove() 호출 시 next()혹은 preivous()에 의해 리턴된 마지막 요소를 리스트에서 제거한다.
1
2
3
4
5
6
case "B" :
        if (it.hasPrevious() && !list.isEmpty()) {
            it.previous();
            it.remove();
        }
        break;

결과

참고 사이트