[BoJ][JAVA] 1406 - 에디터, 스택과 배열로 풀어보기

문제 설명

입출력 예시

문제 링크: https://www.acmicpc.net/problem/1406

---

🔎 리뷰 🔍

체감 난이도: ⭐️⭐️
⭐️ - EZ
⭐️⭐️ - 고민 좀 했다..
⭐️⭐️⭐️ - 못풀었다… 해설 봤음
⭐️⭐️⭐️⭐️ - 해설 봐도 모르겠어
⭐️⭐️⭐️⭐️⭐️ - 이거 어떻게 풀었지 내가..?

👌🏼 문제 이해

• 입력
  • 영어 소문자만 가능(600,000글자까지)
  • 커서는 문장의 맨 앞, 문장의 맨 뒤, 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉, 길이가 L인 문자열이 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L + 1가지 경우이다.
  • 지원하는 명령어
    • L
    • D
    • B: 커서 왼 쪽에 있는 문자를 삭제(커서가 문장의 맨 앞으면 무시) 삭제로 ㅣㅇㄴ해 커서는 한 칸 왼 쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
    • P $
• 출력
  • 명령이 수행된 결과를 출력한다.

🧑🏻‍💻 내 코드

import java.io.*;
import java.util.HashMap;
import java.util.Stack;

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 input = br.readLine();
        int cmdCycle = Integer.parseInt(br.readLine());
        Stack<Character> leftS = new Stack<>();
        Stack<Character> rightS = new Stack<>();
        
        // 초기 셋팅(leftStack에 초기화)
        for (int i = 0; i < input.length(); i++) { // O(n)
            leftS.push(input.charAt(i));
        }

		// 명령 수행
        for (int i = 0; i < cmdCycle; i++) { // O(n)
            String cmd = br.readLine();
            switch (cmd.charAt(0)) {
                case 'L': // todo: 왼->오 복사, 왼 pop
                    if (!leftS.isEmpty())
                        rightS.push(leftS.pop());
                    break;
                case 'D': // todo: 오->왼 복사, 오른 pop
                    if (!rightS.isEmpty())
                        leftS.push(rightS.pop());
                    break;
                case 'B': // todo: 왼 pop
                    if (!leftS.isEmpty())
                        leftS.pop();
                    break;
                case 'P': // todo: 문자를 왼에 push
                    leftS.push(cmd.charAt(2));
                    break;
                default: // 정해진 명령 외의 입력이 발생한 경우
                    return; // 종료
            }
        }

        // leftS의 모든 내용을 rightS로 이동
        while (!leftS.isEmpty()) {
            rightS.push(leftS.pop());
        }

        // rightS의 내용을 출력하면 올바른 순서가 됨
        while (!rightS.isEmpty()) {
            bw.write(rightS.pop());
        }

        bw.flush(); // 출력
        bw.close();
    }
}

📜 나만의 해설

• 배열로 푸는 방법,
  • 배열로는 1번부터 input의 length+1까지 홀수 번째에 공백을 채우고 나머지 짝수 변째에 문자열을 입력한다. 이런 식으로 cursor가 공백으로 이동하며, 오른쪽을 삭제하든, 왼쪽을 삭제하든 2개씩 삭제하고 2개씩 추가하는 방법으로 명령을 수행한 뒤, 출력할 수 있겠다는 생각을 했지만 Stack으로 풀기 위해 이 방법은 실행하지 않았다.
• 스택으로 푸는 방법,
  • 위 문제는 필자의 생각으론, 세 가지 개념을 사용하려고 한다.
  • leftStack - 커서위치 - rightStack
  • 위처럼 두어 커서를 이동하는 것이 아니라 leftStack의 top과 rightStack의 top을 서로 이동하는 식으로 커서 이동을 구현해봤다.
  • 스택 사이의 요소 이동을 통한 커서 구현은 코드의 주석에서 자세히 설명해두었으니 확인해주시기 바랍니다!