[백준 - Java] 문제 1406 : 에디터

접근 방식

명령어에 따라 추가/제거 작업이 행해져야 하기 때문에 연결리스트 사용하기로 선택

• 배열            : O(N)
• 연결리스트 : O(1)   시간복잡도 유리

제출

코드

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        LinkedList<Character> list = new LinkedList<Character>();
        int cursor = 0;

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

        int num = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < num; i++) {
            String mode = sc.nextLine();
            if(mode.charAt(0) == 'P') {
                list.add(cursor, mode.charAt(2));
                cursor++;
            } else if (mode.charAt(0) == 'L') {
                if(cursor != 0)
                    cursor--;
            } else if (mode.charAt(0) == 'D') {
                if(cursor != list.size())
                    cursor++;
            } else if (mode.charAt(0) == 'B') {
                if(cursor != 0) {
                    list.remove(cursor - 1);
                    cursor--;
                }
            } else {
                System.out.println("잘못된 입력입니다.");
                break;
            }
        }
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i));
        }
    }
}

결과

해결 방안

효율적인 입출력을 위해 BufferedReader / BufferedWriter를 사용해 봤다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        LinkedList<Character> list = new LinkedList<Character>();

        int cursor = 0;
        String str = br.readLine();

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

        int num = Integer.parseInt(br.readLine());
        for (int i = 0; i < num; i++) {
            String mode = br.readLine();
            if(mode.charAt(0) == 'P') {
                list.add(cursor, mode.charAt(2));
                cursor++;
            } else if (mode.charAt(0) == 'L') {
                if(cursor != 0)
                    cursor--;
            } else if (mode.charAt(0) == 'D') {
                if(cursor != list.size())
                    cursor++;
            } else if (mode.charAt(0) == 'B') {
                if(cursor != 0) {
                    list.remove(cursor - 1);
                    cursor--;
                }
            } else {
                bw.write("잘못된 입력입니다.");
                break;
            }
        }
        for (int i = 0; i < list.size(); i++) {
            bw.write(list.get(i));
        }
        bw.flush();
        bw.close();
    }
}

채점 결과

여전히 [시간 초과]가 떴다.

어떻게 해결할까 검색을 하다가 ListIterator 인터페이스를 활용하면 가능하다고 해서 사용해 보았다.

https://mygumi.tistory.com/62

ListIterator 인터페이스 활용하기 :: 마이구미

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        LinkedList<Character> list = new LinkedList<Character>();

        String str = br.readLine();

        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        ListIterator<Character> iter = list.listIterator();
        while (iter.hasNext()) {
            iter.next();
        }
        
        int num = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < num; i++) {
            String mode = br.readLine();
            
            if(mode.charAt(0) == 'P') {
                iter.add(mode.charAt(2));
            } else if (mode.charAt(0) == 'L') {
                if(iter.hasPrevious())
                    iter.previous();
            } else if (mode.charAt(0) == 'D') {
                if(iter.hasNext())
                    iter.next();
            } else if (mode.charAt(0) == 'B') {
                if(iter.hasPrevious()) {
                    iter.previous();
                    iter.remove();
                }
            } else {
                break;
            }
        }
        for(Character chr : list) {
            bw.write(chr);
        }
        bw.flush();
        bw.close();
    }
}

채점 결과

결과

ListIterator의 유무도 시간초과의 한몫을 차지했지만, 여러 번의 실험 끝에 List를 출력하는 코드 또한 시간초과 결과를 얻는데 큰 비중을 차지한 것 같다.

// 결과 : 시간초과 - for문
for (int i = 0; i < list.size(); i++) {
            bw.write(list.get(i));
        }

// 결과 : 통과 - for each 문
for(Character chr : list) {
            bw.write(chr);
        }