[Java] 백준 1406번 : 에디터*

1. 문제

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

1406번: 에디터

 

 

2. 풀이 과정

[방법1] LinkedList + Iterator

처음에는 LinkedList를 사용해서 풀었다. LinkedList를 선택한 이유는 리스트 중간에 값을 삽입하고 삭제하는 과정이 빠르기 때문이다. 하지만 시간초과가 났다.

기존 코드에서는 커서가 있는 값을 index를 써서 해당 위치에 있는 값을 찾았기 때문에, LinkedList는 맨 처음 요소부터 index번째에 있는 위치를 하나씩 찾아가기 때문에 시간이 오래걸렸기 때문이다. 따라서 여기에 Iterator를 사용해서 풀었더니 성공했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        LinkedList<Character> result = new LinkedList<>();
        String input = br.readLine();
        int M = Integer.parseInt(br.readLine());

        for(int i=0, size = input.length(); i<size; i++){
            result.add(input.charAt(i));
        }

        ListIterator<Character> iter = result.listIterator();
        while(iter.hasNext()){//커서를 맨 뒤로 이동
            iter.next();
        }

        while(M-- > 0){
            String command = br.readLine();
            switch (command.charAt(0)){
                case 'L':
                    if(iter.hasPrevious()){
                        iter.previous();
                    }
                    break;
                case 'D':
                    if(iter.hasNext()){
                        iter.next();
                    }
                    break;
                case 'B':
                    if(iter.hasPrevious()){
                        iter.previous();
                        iter.remove();
                    }
                    break;
                case 'P':
                    iter.add(command.charAt(2));
                    break;
            }

        }

        StringBuilder sb = new StringBuilder();
        for(char c : result){
            sb.append(c);
        }
        System.out.println(sb);

    }

}

 

결과

 

 

[방법2] Stack

stack으로 풀이하는 방법은 처음부터 떠오르지 않았고, 질문 보기의 키워드에 stack이 있는 것을 보고 생각하여 풀었다.

커서를 기준으로 왼쪽에 있는 값을 ls로 오른쪽에 있는 값을 rs에 넣는 방식이다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String input = br.readLine();
        int M = Integer.parseInt(br.readLine());

        Stack ls = new Stack();
        Stack rs = new Stack();

        for(char c : input.toCharArray())
            ls.push(c);

        while(M-- > 0){
            String command = br.readLine();
            switch (command.charAt(0)){
                case 'L':
                    if(!ls.isEmpty()){
                        rs.push(ls.pop());
                    }
                    break;
                case 'D':
                    if(!rs.isEmpty()){
                        ls.push(rs.pop());
                    }
                    break;
                case 'B':
                    if(!ls.isEmpty()){
                        ls.pop();
                    }
                    break;
                case 'P':
                    ls.push(command.charAt(2));
                    break;
            }

        }

        while(!ls.isEmpty()){
            rs.push(ls.pop());
        }
        while(!rs.isEmpty()){
            sb.append(rs.pop());
        }
        System.out.println(sb);

    }

}

 

결과