[Java] 백준 BOJ / 1406번: 에디터

에디터

문제에서 요구하는 동작은 간단하게 4가지이다.

1. 커서를 왼쪽으로 옮기기
2. 커서를 오른쪽으로 옮기기
3. 커서 왼쪽의 문자 삭제
4. 커서 왼쪽에 문자 삽입

---

첫번째 시도 (실패)

간단하게 LinkedList로 구현하기로 하고 index를 선언 후 해당 Index를 가지고 커서의 위치를 판별하는 식으로 진행했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int index;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

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

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


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

        index = str.length();

        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String c = st.nextToken();
            switch (c) {
                case "L":
                    if (index > 0) {
                        index--;
                    }
                    break;

                case "D":
                    if (index < q.size()) {
                        index++;
                    }
                    break;

                case "B":
                    if (index > 0) {
                        q.remove(--index);
                    }
                    break;

                case "P":
                    String char_item = st.nextToken();
                    Character ch = char_item.charAt(0);
                    q.add(index++, ch);
                    break;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Character c : q) {
            sb.append(c);
        }

        System.out.println(sb);
    }
}

그러나 시간초과가 뜨고 말았는데 질문게시판을 보니

자바의 LinkedList는 인덱스 노드를 가지지 않기 때문에 전부 탐색을 한다.

라는 글이 있어서 방향을 바꾸기로 했다.

---

두번째 시도

그래서 인덱스 커서를 유지하면서 이 문제를 풀 방법을 고민을 해보았는데 양방향 큐를 두개 구현해서 커서가 없지만 있는 것 처럼 구현할 수 있을 것 같아서 두개의 덱을 사용하여 문제를 풀기로 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    static int n;

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

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

        Deque<Character> left = new LinkedList<>();
        Deque<Character> right = new LinkedList<>();


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

        left_index = str.length();
        right_index = str.length();

        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String c = st.nextToken();

            switch (c) {
                case "L":
                    if (!left.isEmpty()) {
                        right.addFirst(left.removeLast());
                    }
                    break;

                case "D":
                    if (!right.isEmpty()) {
                        left.addLast(right.removeFirst());

                    }
                    break;

                case "B":
                    if (!left.isEmpty())
                        left.removeLast();
                    break;

                case "P":
                    String char_item = st.nextToken();
                    Character ch = char_item.charAt(0);
                    left.addLast(ch);
                    break;
            }
        }

        StringBuilder sb = new StringBuilder();

        for (Character c : left) {
            sb.append(c);
        }

        for (Character c : right) {
            sb.append(c);
        }

        System.out.println(sb);
    }
}

해당 문제와 같이 left와 right의 이름을 가진 두개의 덱을 사용하여 커서의 위치에 따라 왼쪽덱, 오른쪽덱이 구분되게 하니 성공할 수 있었다.

자료구조를 더 공부하고 특성을 잘 활용할 수 있어야 할 것 같다.