[BOJ-JAVA] 1406번: 에디터

문제 해결

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

1406번: 에디터

연결리스트 사용

• 커서를 사용하여 이동하며 삽입, 삭제 등의 행동을 하기 때문에 연결리스트로 초기 구현했다.
• 하지만 시간초과가 발생!
  • System.out.print 부분을 StringBuilder로 변경해줬지만 역시나 시간초과
  • cursor라는 변수를 두어 삽입, 삭제를 진행하는데 연결리스트는 처음부터 노드를 하나씩 살피기 때문에 시간이 오래걸리는 것 같아, iterator를 사용해보기로함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] word = br.readLine().toCharArray();
        List<Character> list = new LinkedList<Character>();
        for(int i=0; i<word.length; i++) {
            list.add(word[i]);
        }
        int N = Integer.valueOf(br.readLine());
        int cursor = list.size();
        while(N-- > 0) {
            String[] orders = br.readLine().split(" ");
            switch (orders[0]) {
                case "L":
                    if (cursor != 0) {
                        cursor--;
                    }
                    break;
                case "D":
                    if (cursor <= list.size()) {
                        cursor++;
                    }
                    break;
                case "B":
                    if (cursor != 0) {
                        list.remove(--cursor);
                    }
                    break;
                case "P":
                    if(cursor > list.size()){
                        list.add(orders[1].charAt(0));
                    }
                    else{
                        list.add(cursor, orders[1].charAt(0));
                    }
                    cursor++;
                    break;

            }
        }
        for(int i=0; i< list.size(); i++){
            System.out.print(list.get(i));
        }
    }
}

 

연결리스트 iterator 사용

• iterator를 사용했을 때 시간초과 없이 성공
• 여기서 iterator는 cursor의 오른쪽 문자를 가리키고 있다고 생각
  • cursor는 두 문자 사이에 존재하기 때문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] word = br.readLine().toCharArray();
        List<Character> list = new LinkedList<Character>();
        for(int i=0; i<word.length; i++) {
            list.add(word[i]);
        }

        int N = Integer.valueOf(br.readLine());
        ListIterator<Character> cursor = list.listIterator();
        while(cursor.hasNext()){
            cursor.next();
        }
        while(N-- > 0) {
            String[] orders = br.readLine().split(" ");
            switch (orders[0]) {
                case "L":
                    if (cursor.hasPrevious()) {
                        cursor.previous();
                    }
                    break;
                case "D":
                    if (cursor.hasNext()) {
                        cursor.next();
                    }
                    break;
                case "B":
                    if (cursor.hasPrevious()) {
                        cursor.previous();
                        cursor.remove();
                    }
                    break;
                case "P":
                    cursor.add(orders[1].charAt(0));
                    break;

            }
        }
        StringBuilder sb = new StringBuilder();
        for(Character chr: list){
            sb.append(chr);
        }
        System.out.println(sb);

    }
}

 

Stack 사용 방법

• cursor를 기준으로 왼쪽과 오른쪽을 각가 stack을 두어 해결가능
• stack의 시간복잡도는 O(1)을 가지기 때문에 시간초과에 걸리지 않음
• 커서 기준 왼쪽 오른쪽이 나눠져서 좀 더 직관적!