1406 자바 ] 에디터(풀이)

※ 문제

출처 : (https://www.acmicpc.net/problem/1406)

---

1. 실패 코드

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

public class Main {
    static LinkedList<String> list = new LinkedList<>();

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

        String str = br.readLine();
        String[] arr = str.split("");
        int position = arr.length;
        for(int i=0; i<arr.length; i++) {
            list.add(arr[i]);
        }


        int N = Integer.parseInt(br.readLine());
        String temp1, temp2 = null;
        while(N-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            temp1 = st.nextToken();
            if(temp1.equals("P")) temp2 = st.nextToken();
            else temp2 = "";

            switch(temp1) {
                case "P" :
                    if(position == list.size()) {
                        list.add(temp2);
                        position++;
                    } else {
                        list.add(position, temp2);
                        position++;
                    }
                    break;
                case "L" :
                    if(position > 0) position--;
                    break;
                case "D" :
                    if(position < list.size()) position++;
                    break;
                default :
                    if(position > 0) {
                        position--;
                        list.remove(position);
                    }
                    break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(String listStr : list) {
            sb.append(listStr);
        }

        System.out.println(sb);
    }
}

 - 아마 많은 분들이 LinkedList를 이용해서 푼 경우 시간초과가 발생하였을 것이다. 이유는 LinkedList는 제공된 함수를 이용해 필요한 인덱스의 접근하는 경우 처음부터 끝까지 노드를 타고 이동해야하기 때문에 빠른 처리에는 용이하지 않다.

 

간단하게 List 자료구조의 차이에 대한 포스팅을 참고바란다.

https://jfbta.tistory.com/87

자료구조 ] Vector, ArrayList, LinkedList 의 차이 정리

그래서 처음부터 끝까지 노드를 타고 이동해서 검색하는 것이 아닌 문제처럼 커서 위치에서 시작하는 방법이 있다. 그것은 ListIterator를 사용하면 된다.

 

보통 자주 사용되는 Iterator는 단방향이기 때문에 적합하지 않지만 ListIterator는 양방향 이기 때문에 이번 문제를 푸는데 적합하다.

2. 성공 코드

import java.io.*;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    static LinkedList<String> list = new LinkedList<>();

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

        /*list 세팅*/
        String str = br.readLine();
        String[] arr = str.split("");
        for(int i=0; i<arr.length; i++) {
            list.add(arr[i]);
        }

        /*문자의 맨 뒤로 이동*/
        ListIterator<String> iter = list.listIterator();
        while(iter.hasNext()) {
            iter.next();
        }

        int N = Integer.parseInt(br.readLine());
        while(N-->0) {
            String strSub = br.readLine();

            switch(strSub.charAt(0)) {
                case 'P' :
                    iter.add(String.valueOf(strSub.charAt(2)));
                    break;
                case 'L' :
                    if(iter.hasPrevious()) iter.previous();
                    break;
                case 'D' :
                    if(iter.hasNext()) iter.next();
                    break;
                default :
                    if(iter.hasPrevious()) {
                        iter.previous();
                        iter.remove();
                    }
                    break;
            }
        }

        for(String listStr : list) {
            bw.write(listStr);
        }

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