백준 1406 에디터 파이썬

백준 에디터 1406 파이썬

문제 설명

문제

한 줄로 된 문자열과 입력 명령들이 주어진다. 커서는 문자의 사이(맨 앞과 맨 뒤 포함)에 위치할 수 있다. 아래의 명령어를 수행하는 프로그램을 작성하시오.

• L : 커서를 왼쪽으로 한 칸 옮김 (커서가 맨 앞이면 무시됨)
• D : 커서를 오른쪽으로 한 칸 옮김 (커서가 맨 뒤이면 무시됨)
• B : 커서 왼쪽에 있는 문자를 삭제함 (커서가 맨 앞이면 무시됨)
• P $ : $라는 문자를 커서 왼쪽에 추가함

---

테스트케이스

abcd
3
P x
L
P y

---

문제 작동원리

초기 상태 (문자열 abcd, 커서는 맨 뒤에 위치)

a b c d _

• 문자열이 abcd이고, _는 커서를 의미합니다.
• 입력 직후에는 항상 커서가 문자열 맨 끝에 있습니다.

---

(1) P x 실행

• 명령어 P는 문자를 커서 왼쪽에 삽입합니다.
• 현재 커서는 맨 뒤(_)에 있으므로, `'x'`가 `'d'` 뒤에 삽입됩니다.

a b c d x_

• 따라서 문자열은 `"abcdx"`가 되고, 커서는 여전히 `'x'` 뒤에 있습니다.

---

(2) L 실행

• 명령어 L은 커서를 왼쪽으로 한 칸 이동시킵니다.
• 원래 커서는 `'x'` 뒤에 있었는데, 한 칸 왼쪽으로 이동하면서 `'x'`의 앞, 즉 `'d'`와 `'x'` 사이로 이동합니다.

a b c d _ x

• 이제 커서는 `'d'`와 `'x'` 사이에 있습니다.

---

(3) P y 실행

• 명령어 P는 문자를 커서 왼쪽에 삽입합니다.
• 현재 커서는 `'d'`와 `'x'` 사이에 있으므로, `'y'`가 그 위치에 삽입됩니다.

a b c d y_ x

• 따라서 최종 문자열은 `"abcdyx"`가 됩니다.

---

문제풀이 아이디어

이 문제는 문자열 편집기를 구현하는 시뮬레이션 문제입니다. 문자열의 중간 삽입, 삭제, 커서 이동을 빠르게 처리해야 하므로 연결리스트(list 컨테이너)를 사용하는 것이 적합합니다.

• 파이썬의 이중 연결 리스트를 직접 구현하여 삽입과 삭제가 O(1) 시간에 가능하도록 합니다.
• 커서는 노드를 가리키는 변수로 표현합니다.
• 커서의 이동은 `lt.prev`, `lt.next`로 처리합니다.
• `erase`와 `insert`는 커서가 가리키는 노드를 기준으로 처리됩니다.

---

전체코드

import sys

class Node:
    def __init__(self, ch=None):
        self.ch = ch
        self.prev = None
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def insert(self, lt, ch):
        new_node = Node(ch)
        prev_node = lt.prev
        prev_node.next = new_node
        new_node.prev = prev_node
        new_node.next = lt
        lt.prev = new_node

    def erase(self, lt):
        if lt.prev == self.head:
            return lt
        target = lt.prev
        target.prev.next = lt
        lt.prev = target.prev
        return lt

    def to_string(self):
        cur = self.head.next
        result = []
        while cur != self.tail:
            result.append(cur.ch)
            cur = cur.next
        return "".join(result)

arr = sys.stdin.readline().strip()
N = int(sys.stdin.readline().strip())

st = LinkedList()
for c in arr:
    st.insert(st.tail, c)

lt = st.tail

for _ in range(N):
    cmd = sys.stdin.readline().strip().split()
    k = cmd[0]

    if k == 'L' and lt.prev != st.head:
        lt = lt.prev
    elif k == 'D' and lt != st.tail:
        lt = lt.next
    elif k == 'B':
        lt = st.erase(lt)
    elif k == 'P':
        ch = cmd[1]
        st.insert(lt, ch)

print(st.to_string())

---

개별코드

1. 초기 문자열 입력 및 리스트 생성

st = LinkedList()
for c in arr:
    st.insert(st.tail, c)

lt = st.tail

• 입력받은 문자열을 직접 구현한 LinkedList에 삽입합니다.
• 커서(lt)는 리스트의 더미(dummy) 테일 노드에서 시작합니다. 이는 C++의 list::end()와 같은 역할을 합니다.

---

2. 명령어 처리

if k == 'L' and lt.prev != st.head:
    lt = lt.prev

• L: 커서 노드의 이전 노드로 이동.

elif k == 'D' and lt != st.tail:
    lt = lt.next

• D: 커서 노드의 다음 노드로 이동.

elif k == 'B':
    lt = st.erase(lt)

• B: 커서 왼쪽 문자를 삭제. 직접 구현한 erase 메소드를 호출하여 삭제하고, 반환되는 노드를 새로운 커서 위치로 갱신합니다.

elif k == 'P':
    ch = cmd[1]
    st.insert(lt, ch)

• P: 입력받은 문자를 커서 왼쪽에 삽입.

---

3. 최종 출력

print(st.to_string())

• to_string() 메소드를 호출하여 리스트 전체를 문자열로 변환한 뒤 출력합니다.

---

결론

이 문제의 핵심은 문자열 중간 삽입·삭제를 효율적으로 처리하기 위해 **연결 리스트(LinkedList)**를 직접 구현하고, **노드를 커서처럼 사용**하는 점입니다.

• 연결 리스트는 삽입/삭제가 O(1)이라 빠릅니다.
• 노드 객체 lt를 커서로 두어 위치를 쉽게 이동할 수 있습니다.
• erase와 insert 메소드를 통해 리스트 구조를 올바르게 조작해야 합니다.

👉 결국 이 문제는 **연결 리스트의 기본 동작과 파이썬 클래스 활용 능력**을 이해하는 것이 핵심입니다.