[백준] 문제 1406번 : 에디터 - JAVA

[링크] : https://www.acmicpc.net/problem/1406

 

---

 

 

💎 문제 분석 & 제약 조건

 

문제 분석:

 

텍스트 편집기의 기능을 구현하는 문제로, 주어진 문자열에 대해 일련의 명령어를 처리하고, 그 결과 최종 문자열을 구하는 문제

 

주어진 명령어에는 커서 이동, 문자 삽입 및 삭제가 포함된다.

 

주요 작업은 커서를 왼쪽, 오른쪽으로 이동하거나, 커서 앞에 문자를 삭제하거나 삽입하는 것

 

커서 이동 및 문자열 삽입/삭제가 중요하다. 문제의 요구사항은 스택, 덱, Iterator 를 이용 가능한데, 덱이 양방향 큐로 문제

 

에서 요구하는 양방향으로 움직이는 커서를 구현하기에 적합하고 , Iterator를 사용했을때 수정, 삭제가 많이 일어나면

 

성능상 느리기 때문에 덱을 이용하여 구현하는 것이 이 문제에서는 적합하다고 생각했다.

 

 

 

제약 조건:

 

입력 문자열의 길이: N (1 ≤ N ≤ 100,000)

 

명령어의 수: M (1 ≤ M ≤ 500,000)

 

 

 

---

🚀 의사 결정

 

1. 효율적으로 커서를 관리하고 명령어를 빠르게 처리 하기 위해 Deque 자료 구조를 사용 결정

 

 - 양방향 큐로, 양쪽 끝에서 삽입과 삭제 시, Iterator 보다 시간이 적게 걸리고 Stack 보다 구현이 쉽다.

 

 - 문자열의 앞부분과 뒷부분 처리할 때 덱이 효율적이고, 커서를 양 끝에서 자유롭게 이동하면서 문자 삽입과 삭제를 빠르  게 할 수 있다.

 

2. BufferdReader로 입력을 받고 , InputStreamReader를 함께 사용해서 시간 단축, 메모리 효율을 높인다.

 

3. Deque 을 두 개의 스택으로 분리하여 관리

    - 하나는 왼쪽 스택: 커서 왼쪽에 있는 문자들을 저장

    - 하나는 오른쪽 스택: 커서 오른쪽에 있는 문자들을 저장

    - 각 명령어는 Deque의 양쪽 끝에서 효율적으로 삽입/삭제를 수행하며, 커서를 왼쪽, 오른쪽으로 이동시킬 수 있다.

 

4. 명령어 처리

'L': 커서를 왼쪽으로 한 칸 이동 - 왼쪽 스택에서 하나를 오른쪽 스택으로 옮긴다.

'D': 커서를 오른쪽으로 한 칸 이동 - 오른쪽 스택에서 하나를 왼쪽 스택으로 옮긴다.

'B': 커서 앞의 문자 삭제 - 왼쪽 스택에서 문자를 하나 삭제한다.

'P x': 커서 앞에 문자 x 삽입 - 왼쪽 스택에 문자를 삽입한다.

 

5. StringBuilder 를 이용해서 최종적으로 leftDeque와 rightDeque 문자들을 한번에 합쳐서 출력한다.

 

 

---

📜 소스코드(Java)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 초기 문자열 입력 받기
        String str = br.readLine();
        int M = Integer.parseInt(br.readLine());  // 명령어의 개수

        // Deque 사용: 왼쪽 부분과 오른쪽 부분을 분리하여 관리
        Deque<Character> leftDeque = new ArrayDeque<>();
        Deque<Character> rightDeque = new ArrayDeque<>();

        // 문자열을 leftDeque에 모두 넣기
        for (char c : str.toCharArray()) {
            leftDeque.addLast(c);
        }

        // 명령어 처리
        for (int i = 0; i < M; i++) {
            String command = br.readLine();
            char cmd = command.charAt(0);  // 명령어의 첫 글자

            switch (cmd) {
                case 'L':  // 커서를 왼쪽으로 한 칸 이동
                    if (!leftDeque.isEmpty()) {
                        rightDeque.addFirst(leftDeque.pollLast());  // leftDeque의 마지막 문자를 오른쪽 deque의 앞에 추가
                    }
                    break;
                case 'D':  // 커서를 오른쪽으로 한 칸 이동
                    if (!rightDeque.isEmpty()) {
                        leftDeque.addLast(rightDeque.pollFirst());  // rightDeque의 첫 문자를 왼쪽 deque의 뒤에 추가
                    }
                    break;
                case 'B':  // 커서 왼쪽에 있는 문자 삭제
                    if (!leftDeque.isEmpty()) {
                        leftDeque.pollLast();  // 왼쪽 deque의 마지막 문자 삭제
                    }
                    break;
                case 'P':  // 문자를 삽입
                    char ch = command.charAt(2);  // 삽입할 문자
                    leftDeque.addLast(ch);  // 커서 위치에 문자를 추가 (leftDeque에 삽입)
                    break;
                default:
                    break;
            }
        }

        // 최종적으로 leftDeque와 rightDeque의 문자들을 합쳐서 출력
        StringBuilder result = new StringBuilder();

        // leftDeque의 모든 문자를 result에 추가
        while (!leftDeque.isEmpty()) {
            result.append(leftDeque.pollFirst());
        }

        // rightDeque의 모든 문자를 result에 추가
        while (!rightDeque.isEmpty()) {
            result.append(rightDeque.pollFirst());
        }

        System.out.println(result.toString());
    }
}

 

---