[정글 알고리즘] - [하] - 백준 1406번 실버 II 연결 리스트(Linked List) - 에디터

 

커서가 있는 텍스트 에디터를 구현하는 문제입니다.
단방향 연결 리스트로는 왼쪽 이동이 O(N)이라 시간 초과 → 이중 연결 리스트로 O(1) 구현합니다.
핵심: 더미 head·tail 노드로 경계를 단순화합니다.

📋 문제 정보

항목	내용
문제 번호	백준 1406번
난이도	🟢 실버 II
알고리즘	이중 연결 리스트, 자료구조 설계
입력	첫 줄: 초기 문자열 (최대 100,000자) 둘째 줄: 명령어 수 M (1 ≤ M ≤ 500,000) 이후 M줄: L / D / B / P $ 명령
출력	모든 명령 수행 후 편집기에 남은 문자열
커서 초기 위치	문자열 맨 뒤

⌨️ 4가지 명령어

명령	설명	예시	예외 (무시)
L	커서를 왼쪽으로 한 칸	abc| → ab|c	커서가 맨 앞이면 무시
D	커서를 오른쪽으로 한 칸	ab|c → abc|	커서가 맨 뒤이면 무시
B	커서 왼쪽 문자 삭제	ab|c → a|c	커서가 맨 앞이면 무시
P $	커서 왼쪽에 문자 $ 삽입	ab|c + P x → abx|c	항상 실행

❌ 왜 단방향 연결 리스트는 안 되는가?

문제	단방향	이중 연결 리스트
L 명령 (왼쪽 이동)	head부터 재탐색 → O(N)	cursor.prev 한 번 → O(1)
B 명령 (삭제)	이전 노드 찾으러 재탐색 → O(N)	cursor.prev 바로 접근 → O(1)
전체 M=500,000	O(N×M) = 최악 O(3×10¹⁰) → TLE	O(M) = O(500,000) → 통과

💡 더미 head·tail 노드 전략

실제 문자를 담지 않는 더미(Dummy) 노드를 맨 앞(head)과 맨 뒤(tail)에 배치합니다.
이렇게 하면 경계 조건(맨 앞/맨 뒤 예외처리)이 획기적으로 단순해집니다.

head 더미 (data='')

⇄

a

⇄

b

⇄

c ← cursor

⇄

tail 더미 (data='')

더미 노드 없을 때	더미 노드 있을 때	효과
if cursor == None: 맨 앞/뒤 특수처리	if cursor == head: 한 줄 비교	경계 조건 단순화
삽입 시 head 갱신 별도 처리	항상 동일한 삽입 로직 사용	코드 일관성 ↑

🔧 이중 연결 리스트 노드 구조

단방향 (기존)	이중 연결 (추가)	차이
self.data self.next	self.data self.prev self.next	self.prev 추가 → 왼쪽 노드 O(1) 접근

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None   # ← 이전 노드 포인터 (이중 연결 리스트의 핵심)
        self.next = None

🔍 초기화 과정 시각화 (입력: "abc")

① 더미 노드 생성 및 연결

head ('')

⇄

tail ('')

② 'a' 삽입 (cursor=head → cursor=a)

head

⇄

a ← cursor

⇄

tail

③ 'b', 'c' 삽입 완료 (cursor=c → 문자열 맨 끝)

head

⇄

a

⇄

b

⇄

c ← cursor

⇄

tail

커서는 항상 커서 왼쪽 노드를 가리킵니다. cursor=c 이면 에디터 상태는 abc|

⚙️ 4가지 연산 구조 비교

L — 왼쪽 이동

head

⇄

a

⇄

b ← cursor (전)

⇄

c

⇄

tail

↓ L 명령

head

⇄

a ← cursor (후)

⇄

b

⇄

c

⇄

tail

if cursor != head:
    cursor = cursor.prev   # 맨 앞(head)이면 무시

D — 오른쪽 이동

head

⇄

a ← cursor (전)

⇄

b

⇄

c

⇄

tail

↓ D 명령

head

⇄

a

⇄

b ← cursor (후)

⇄

c

⇄

tail

if cursor.next != tail:
    cursor = cursor.next   # 맨 뒤(tail 직전)이면 무시

B — 커서 왼쪽 삭제

head

⇄

a

⇄

b 삭제 대상

⇄

c ← cursor

⇄

tail

↓ B 명령 (cursor=c 일 때, b 삭제)

head

⇄

a ← cursor (후)

⇄

c

⇄

tail

if cursor != head:
    delete_node = cursor          # 삭제할 노드 = cursor
    left_node  = delete_node.prev
    right_node = delete_node.next

    left_node.next  = right_node  # left ↔ right 연결
    right_node.prev = left_node

    cursor = left_node            # 커서를 왼쪽으로 이동

P $ — 커서 왼쪽에 삽입

head

⇄

a ← cursor

⇄

b

⇄

tail

↓ P x 명령 (cursor=a 일 때, x 삽입)

head

⇄

a

⇄

x (새 노드) ← cursor (후)

⇄

b

⇄

tail

ch = command[2]             # 'P x' → command[2] = 'x'
new_node = Node(ch)
right_node = cursor.next    # cursor 오른쪽 노드

new_node.prev = cursor
new_node.next = right_node

cursor.next     = new_node
right_node.prev = new_node

cursor = new_node           # 커서를 새 노드로 이동

🎬 단계별 시뮬레이션

입력:
abcd
3
L
B
P x

단계	명령	커서 위치	리스트 상태	동작
초기	—	d (맨 끝)	H-a-b-c-d|-T	초기 문자열 입력 후 cursor=d
1	L	c	H-a-b-c|-d-T	cursor = cursor.prev (d→c)
2	B	b	H-a-b|-d-T	c 삭제, cursor = b
3	P x	x (새 노드)	H-a-b-x|-d-T	b와 d 사이에 x 삽입, cursor=x

✅ 최종 출력: abxd (head·tail 더미 노드 제외, 중간 노드만 출력)

✅ 최종 풀이 코드 (주석 포함)

# 연결 리스트 - 에디터 (백준 실버2)
# 문제 링크: https://www.acmicpc.net/problem/1406
import sys
input = sys.stdin.readline

# ── 노드 클래스 (이중 연결 리스트) ──────────────────
class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None   # 이전 노드 포인터
        self.next = None   # 다음 노드 포인터

# ── 입력 ──────────────────────────────────────────
text = input().rstrip()
m    = int(input())

# ── 더미 head·tail 생성 및 연결 ───────────────────
head = Node('')
tail = Node('')
head.next = tail
tail.prev = head

# ── 초기 문자열을 한 글자씩 삽입 ─────────────────
cursor = head
for ch in text:
    new_node = Node(ch)

    new_node.prev = cursor        # new ← cursor
    new_node.next = tail          # new → tail
    cursor.next   = new_node      # cursor → new
    tail.prev     = new_node      # tail.prev ← new

    cursor = new_node             # 커서를 새 노드로 전진

# ── 명령 처리 ──────────────────────────────────────
for _ in range(m):
    command = input().rstrip()

    if command[0] == 'L':               # 왼쪽 이동
        if cursor != head:
            cursor = cursor.prev

    elif command[0] == 'D':             # 오른쪽 이동
        if cursor.next != tail:
            cursor = cursor.next

    elif command[0] == 'B':             # 커서 왼쪽 삭제
        if cursor != head:
            delete_node = cursor
            left_node   = delete_node.prev
            right_node  = delete_node.next

            left_node.next  = right_node
            right_node.prev = left_node

            cursor = left_node

    elif command[0] == 'P':             # 커서 왼쪽에 삽입
        ch = command[2]
        new_node   = Node(ch)
        right_node = cursor.next

        new_node.prev   = cursor
        new_node.next   = right_node
        cursor.next     = new_node
        right_node.prev = new_node

        cursor = new_node

# ── 출력 (head.next ~ tail 이전까지) ──────────────
result  = []
current = head.next
while current != tail:
    result.append(current.data)
    current = current.next

print(''.join(result))

🔎 핵심 라인 해설

코드	설명
head = Node('') tail = Node('') head.next = tail tail.prev = head	더미 노드 생성. 실제 데이터 없음. 경계 처리 단순화
cursor = head for ch in text: ...	head부터 시작해 오른쪽으로 삽입. 완료 후 cursor는 맨 끝 문자 노드
if cursor != head	커서가 더미 head면 맨 앞 → 무시. L/B 공통 경계 조건
if cursor.next != tail	커서 오른쪽이 tail이면 맨 끝 → D 명령 무시
ch = command[2]	'P x' → command[0]='P', command[1]=' ', command[2]='x'
cursor = new_node (P 명령 후)	삽입 후 커서는 새 노드로 이동 (삽입 위치 = 커서 왼쪽)
while current != tail	head.next부터 tail 직전까지 순회하며 출력 (더미 제외)

🚨 자주 하는 실수 TOP 5

#	실수	수정
1	ll = LinkedList.append(...) 클래스에 직접 호출	ll = LinkedList() 객체 생성 후 ll.append()
2	for i in range(txt): 문자열에 range 사용	for ch in txt: 문자열 직접 순회
3	단방향 리스트로 L 구현 → O(N) 탐색 → TLE	self.prev 추가 → 이중 연결 리스트로 O(1)
4	P 명령 후 cursor를 new_node로 이동 안 함	삽입 후 반드시 cursor = new_node
5	더미 노드 없이 head/tail 경계 None 비교	더미 head·tail 사용 → 모든 연산 동일 로직 적용

⏱️ 시간복잡도 분석

연산	단방향	이중 연결 리스트	비고
L (왼쪽 이동)	O(N)	O(1)	prev 포인터 덕분
D / B / P	O(1) ~ O(N)	O(1)	모두 포인터 조작만
전체 M 명령	O(N×M) → TLE	O(M) → 통과	M=500,000 기준

🏁 핵심 정리

포인트	내용
🔗	이중 연결 리스트 필수 — prev 포인터로 왼쪽 이동 O(1)
🎭	더미 head·tail — 경계 조건 예외처리 없이 일관된 코드
📍	cursor = 커서 왼쪽 노드 — 항상 이 규칙으로 4가지 명령 통일
⛓️	삽입/삭제 모두 4개 포인터 조작 (prev·next 양쪽)
⏱️	전체 O(M) — 단방향 대비 최악 O(N×M)에서 극적 개선