[알고리즘 PS] 백준 1406 에디터 자바 문제 풀이 (스택 직접 구현해서 풀어보기)

문제

해당 포스팅은 백준의 1406번 에디터 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

문제

예제 입력 & 출력

해결법

이 문제는 사실 여러 방법으로 해결할 수 있는 문제이다.

Cursor이라는 개념은 LinkedList에서 적합해 보이지만 LinkedList를 그대로 사용해서 풀면 시간 초과가 나오게 된다.

그래서 다른 접근을 통해 풀어야 하는데, 그 다른 접근이 바로 스택이다.

접근법

편집기가 지원하는 명령어는 총 4가지 이다.

우리는 커서를 기준으로 Stack 2개로 해당 문제를 풀어갈 수 있다.

 

첫 번째 스택에는 입력한 문자열들이 모두 들어간 채로 시작한다.

그리고 각각의 이동 명령어를 만날 때 마다 커서 왼쪽과 오른쪽 수를 서로 다른 스택에 넣어주면 된다.

 

1. L : 커서를 왼쪽으로 한 칸 옮기는 과정은 왼쪽에 있는 스택에서 수 하나를 빼서 오른쪽으로 옮기면 된다.
2. D : 이도 마찬가지로 오른쪽 스택에서 왼쪽 스택으로 옮기면 된다.
3. B : 커서 왼쪽의 문자이므로 왼쪽 스택에 top을 pop한다.
4. P $ : 커서 왼쪽에 추가하므로 왼쪽 스택에 push 하면 된다.

오답 후보

오답 후보에는 스택이 비어있을 때 pop을 할 수 있으므로 L과 D 연산을 할 때 isEmpty()로 검사를 해줘야 한다.

정답 코드

이번에는 스택을 직접 구현해서 문제를 풀어보려 한다.

연결 리스트로 구현한 스택이다.

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

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 words = br.readLine();
        Stack stack = new Stack();
        char[] word = words.toCharArray();
        for(char ch : word) {
            stack.push(ch);
        }
        Stack tempStack = new Stack();
        int n = Integer.parseInt(br.readLine());
        while(n-- > 0) {

            String cmd = br.readLine();

            if(cmd.charAt(0) == 'P') {
                cmdP(stack, cmd.charAt(2));
            }else {
                if(cmd.charAt(0) == 'L') {
                    cmdL(stack, tempStack);
                }else if(cmd.charAt(0) == 'D') {
                    cmdD(stack, tempStack);
                }else if(cmd.charAt(0) == 'B') {
                    cmdB(stack);
                }
            }
        }

        while(!stack.isEmpty()) {
            tempStack.push(stack.pop());
        }
        while(!tempStack.isEmpty()) {
            bw.write(tempStack.pop());
        }

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

    private static void cmdL(Stack stack, Stack tempStack) {
        if(!stack.isEmpty()) {
            tempStack.push(stack.pop());
        }
    }
    private static void cmdD(Stack stack, Stack tempStack) {
        if(!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
    }
    private static void cmdB(Stack stack) {
        if(!stack.isEmpty()) {
            stack.pop();
        }
    }
    private static void cmdP(Stack stack, char ch) {
        stack.push(ch);
    }
}
class Node {
    private char data;
    private Node link;

    Node(Node link, char data) {
        this.data = data;
        this.link = link;
    }

    char getData() {
        return data;
    }

    Node getLink() {
        return link;
    }
}
class Stack {
    Node top;

    Stack () {
        top = null;
    }
    boolean isEmpty() {
        return top == null;
    }

    void push(char data) {
        top = new Node(top, data);
    }

    char pop() {
        char ret = top.getData();
        top = top.getLink();
        return ret;
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.