[백준] 에디터 (Deque)

문제 소개

에디터 - 백준 1406번 문제를 정리합니다.
이 문제는 간단한 텍스트 에디터를 구현하는 문제로, 문자열 수정 명령어들을 빠르게 처리할 수 있는 자료구조 선택이 핵심입니다.

문제 링크: 에디터 - 백준 1406번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 문자열 중간 삽입, 삭제 연산이 많기 때문에 일반 String 또는 ArrayList로는 시간 초과 발생
2. 커서를 기준으로 왼쪽/오른쪽 문자들을 두 개의 자료구조(스택 or 덱)로 나눠 저장
3. 명령어마다 O(1) 또는 O(1)에 가까운 속도로 처리할 수 있도록 구현

---

해결 과정 및 코드

핵심 아이디어

1. 문자열을 커서를 기준으로 왼쪽(left 덱)과 오른쪽(right 덱)으로 나누어 저장
   • 커서는 항상 left와 right 사이에 있는 것으로 간주
2. 각 명령어는 덱 연산으로 대체:
   • L: left 마지막에서 right 처음 위치으로 문자 이동
   • D: right 처음에서 left 마지막으로 문자 이동
   • B: left 마지막 문자 제거
   • P x: left 마지막 문자 삽입
3. 최종 출력 시 left + right 순으로 문자열 완성

코드

시간 복잡도 :O(N + M)
이유: 초기 문자열 길이 N, 명령어 M개 처리 각각 O(1) 연산으로 구현됨

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

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

        // 커서 기준 왼쪽 문자, 오른쪽 문자 저장
        ArrayDeque<Character> left = new ArrayDeque<>();
        ArrayDeque<Character> right = new ArrayDeque<>();

        // 초기 문자열을 모두 왼쪽 덱에 삽입
        for (char c : br.readLine().toCharArray()) {
            left.offer(c);
        }

        int m = Integer.parseInt(br.readLine());

        // 명령어 처리
        for (int i = 0; i < m; i++) {
            String line = br.readLine();
            char cmd = line.charAt(0);

            if (cmd == 'L') {
                if (!left.isEmpty()) right.push(left.removeLast());
            } else if (cmd == 'D') {
                if (!right.isEmpty()) left.offer(right.removeFirst());
            } else if (cmd == 'B') {
                if (!left.isEmpty()) left.removeLast();
            } else if (cmd == 'P') {
                left.offer(line.charAt(2));
            }
        }

        // 결과 문자열 생성
        for (char c : left) sb.append(c);
        for (char c : right) sb.append(c);
        System.out.println(sb);
    }
}

---

✅ ArrayDeque 메서드 정리표 (진행 방향 + 용도 + 예외 여부)

분류	메서드 이름	방향	동작 설명	실패 시 반환/예외
추가	addFirst(e)	← 왼쪽	앞쪽(Front)에 추가	예외 발생 (IllegalStateException)
	offerFirst(e)	← 왼쪽	앞쪽에 추가 (addFirst와 같지만 실패 시 false)	false 반환
	addLast(e)	→ 오른쪽	뒤쪽(Back)에 추가	예외 발생
	offerLast(e)	→ 오른쪽	뒤쪽에 추가 (addLast와 같지만 실패 시 false)	false 반환
✅	add(e)	→ 오른쪽	= addLast(e) (기본 큐 동작)	예외 발생
✅	offer(e)	→ 오른쪽	= offerLast(e) (기본 큐 동작)	false 반환

---

분류	메서드 이름	방향	동작 설명	실패 시 반환/예외
삭제	removeFirst()	← 왼쪽	앞쪽 원소 제거	예외 발생 (NoSuchElementException)
	pollFirst()	← 왼쪽	앞쪽 원소 제거 (비어있으면 null)	null 반환
	removeLast()	→ 오른쪽	뒤쪽 원소 제거	예외 발생
	pollLast()	→ 오른쪽	뒤쪽 원소 제거 (비어있으면 null)	null 반환
✅	remove()	← 왼쪽	= removeFirst() (기본 큐 동작)	예외 발생
✅	poll()	← 왼쪽	= pollFirst() (기본 큐 동작)	null 반환

---

분류	메서드 이름	방향	동작 설명	실패 시 반환/예외
조회	peekFirst()	← 왼쪽	앞쪽 원소 조회	null 반환
	peekLast()	→ 오른쪽	뒤쪽 원소 조회	null 반환
✅	peek()	← 왼쪽	= peekFirst() (기본 큐 동작)	null 반환
	getFirst()	← 왼쪽	앞쪽 원소 조회	예외 발생
	getLast()	→ 오른쪽	뒤쪽 원소 조회	예외 발생
✅	element()	← 왼쪽	= getFirst() (기본 큐 동작)	예외 발생

---

분류	메서드 이름	방향	동작 설명	실패 시 반환/예외
스택	push(e)	← 왼쪽	앞쪽에 삽입 (스택 push) = addFirst()	예외 발생
	pop()	← 왼쪽	앞쪽에서 제거 (스택 pop) = removeFirst()	예외 발생

---

📝 요약

• add, offer, remove, poll, peek, element는 기본 큐 메서드이며, 내부적으로 대부분 왼쪽(Front) 기준으로 동작
• 스택처럼 쓸 때: push(e) + pop()
• 덱으로 쓸 때: addFirst, addLast, pollFirst, pollLast 등
• 큐로 쓸 때: offer(e), poll(), peek()

---

이제 어떤 상황에서 어떤 메서드를 써야 하는지 명확하게 구분할 수 있을 거예요!
이 표를 이미지로 변환하거나, 다이어그램 형태로 보고 싶으면 말씀해줘요 😊