본문 바로가기
Baekjoon

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

by Chaewon Park 2024. 3. 7.

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

 

1406번: 에디터

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수

www.acmicpc.net


문제


알고리즘

 

일단 가장 먼저 생각했던 방식은 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();
    }
}

'Baekjoon' 카테고리의 다른 글

[백준] 17413번 단어 뒤집기2 (Java)  (0) 2024.03.08
[백준] 1158번 요세푸스 문제 (Java)  (0) 2024.03.06
[백준] 2164번 카드2 (Java)  (1) 2024.02.28
[백준] 1920번 수 찾기 (Java)  (1) 2024.02.27
[백준] 9012번 괄호 (Java)  (3) 2024.02.27