[백준] 1406번 에디터 (Java)

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

1406번: 에디터

---

문제

---

알고리즘

 

일단 가장 먼저 생각했던 방식은 LinkedList를 사용해서 푸는 방법이다!

대충 이런 알고리즘 방식으로 생각했고 다음과 같이 구현했다!

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

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));

        String str = br.readLine(); // 문자 입력
        int N = str.length(); // 문자열 길이
        int M = Integer.parseInt(br.readLine()); // 입력할 명령어 개수
        LinkedList<String> arr = new LinkedList<>();
        int cur = N; // 현재 커서의 위치

        for(int i=0; i<N; i++) {
            arr.add(String.valueOf(str.charAt(i)));
        }

        for(int i=0; i<M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            String command = st.nextToken();

            // 명령 L 이면서 현재 커서가 맨 앞이 아니라면
            if(command.equals("L") && cur != 0) {
                cur--;
            }
            // 명령 D 면서 현재 커서가 맨 뒤가 아니라면
            else if(command.equals("D") && cur != arr.size()) {
                cur++;
            }
            // 명령 B 면서 현재 커서가 맨 앞이 아니라면
            else if(command.equals("B") && cur != 0) {
                cur--;
                arr.remove(cur);
            }
            // 명령 P 라면
            else if(command.equals("P")) {
                arr.add(cur, st.nextToken());
                cur++;
            }
        }

        for(int i=0; i<arr.size(); i++) {
            bw.write(arr.get(i));
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

근데 채점을 해보니 반겨주는 '시간초과'.. 헤

 

 

그래서 다른 방법을 생각한 것이 바로 Stack을 사용해서 푸는 것이다.

 

1. Stack 2개를 만들고 하나는 문자열을 넣고 다른 stack은 남겨둔다.

2. 명령문을 처리한다.

• 명령 L 이라면, stack2로 stack1을 pop()해서 push한다.
• 명령 D 라면, stack2에서 pop()해서 stack1로 push()한다.
• 명령 B 라면, stack1에서 pop()한다.
• 명령 P 라면, stack1에 push()한다.

---

 

코드

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

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));

        String str = br.readLine(); // 문자 입력
        int N = str.length(); // 문자열 길이
        int M = Integer.parseInt(br.readLine()); // 입력할 명령어 개수
        Stack<String> stack1 = new Stack<>();
        Stack<String> stack2 = new Stack<>();

        for(int i=0; i<N; i++) {
            stack1.add(String.valueOf(str.charAt(i)));
        }

        for(int i=0; i<M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            switch(st.nextToken()) {
                case "L" :
                    if(stack1.isEmpty()){
                        break;
                    }
                    stack2.push(stack1.pop());
                    break;
                case "D" :
                    if(stack2.isEmpty()) {
                        break;
                    }
                    stack1.push(stack2.pop());
                    break;
                case "B" :
                    if(stack1.isEmpty()){
                        break;
                    }
                    stack1.pop();
                    break;
                case "P" :
                    stack1.push(st.nextToken());
                    break;
            }
        }

        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }

        while(!stack2.isEmpty()) {
            bw.write(stack2.pop());
        }

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