백준 1406번: 에디터 (Python)

핵심: 스택 2개 사용

🔹 문제 설명

한 줄 에디터 구현 문제

• 최대 600,000글자의 문자열 처리
• 커서 이동 및 문자 편집 기능 구현
• 명령어 종류:
  • L: 커서를 왼쪽으로 한 칸 이동
  • D: 커서를 오른쪽으로 한 칸 이동
  • B: 커서 왼쪽 문자 삭제
  • P $: $ 문자를 커서 왼쪽에 추가
• 초기 커서는 문자열의 맨 끝에 위치
• 입력 제한:
  • 초기 문자열 길이 ≤ 100,000
  • 명령어 개수 ≤ 500,000

---

🔹 내가 처음 작성한 코드

import sys

stack = sys.stdin.readline()    # 초기 문자열
m = int(sys.stdin.readline())    # 명령어 개수
cursor = len(stack)

# L: 왼쪽 이동, D: 오른쪽 이동, B: 삭제, P $: 추가
for _ in range(m):
    command = sys.stdin.readline().strip()
    if command == "L" and cursor > 0:
        cursor -= 1
    elif command == "D" and cursor < len(stack):
        cursor += 1
    elif command == "B" and cursor > 0:
        stack.pop(cursor-1)
        cursor -= 1
    elif len(command) == 3:
        char = command.split()[1]
        stack.insert(cursor, char)
        cursor += 1

for i in stack:
    print(i, end="")

---

🔹 ❌ 문제점 및 오류 분석

1️⃣ stack 초기화 오류

• sys.stdin.readline()은 문자열을 반환.
• pop()과 insert()는 리스트에서만 사용 가능.
• ⚡ 해결: 문자열을 리스트로 변환

  stack = list(sys.stdin.readline().strip())
  

---

2️⃣ 시간 복잡도 문제

• insert()와 pop()가 리스트 중간에서 수행되면 O(N)
• 최대 입력 시 시간 초과 발생 가능
• ⚡ 해결: 스택 2개 사용하여 O(1) 시간 복잡도 유지
  • left_stack: 커서 왼쪽 문자열
  • right_stack: 커서 오른쪽 문자열

---

3️⃣ 명령어 처리 미흡

• B 명령어에서 cursor == 0일 때 IndexError 발생 가능
• P 명령어에서 커서 위치 처리 오류 (cursor-1 대신 cursor 사용 필요)

---

🔹 🔥 최적화된 코드 (스택 2개 사용)

import sys

left_stack = list(sys.stdin.readline().strip())
right_stack = []

m = int(sys.stdin.readline())
for _ in range(m):
    command = sys.stdin.readline().strip()

    if command == "L" and left_stack:
        right_stack.append(left_stack.pop())
    elif command == "D" and right_stack:
        left_stack.append(right_stack.pop())
    elif command == "B" and left_stack:
        left_stack.pop()
    else:
        if command.startswith("P"):
            _, char = command.split()
            left_stack.append(char)

# 결과 출력
print("".join(left_stack + right_stack[::-1]))

---

🔹 ✅ 최적화된 코드의 특징

항목 기존 코드 (실패) 최적화 코드 (성공)

시간 복잡도	O(N) per 명령어 (시간 초과 가능)	O(1) per 명령어 (O(N) 전체)
자료구조	단일 리스트 사용	스택 2개 사용 (left, right)
대용량 처리	최대 600,000자 + 500,000명령어 시 시간 초과	빠르고 효율적 처리 가능
명령어 처리	insert(), pop() 사용	append(), pop()만 사용
출력 처리	반복 출력 (print)	"".join() 사용 (빠른 출력)

---

🔹 📝 최종 요약 및 결론

1️⃣ 문자열 초기화: list()로 문자열을 리스트 형태로 변환
2️⃣ 스택 2개 사용: left_stack과 right_stack으로 커서 위치 처리
3️⃣ 시간 복잡도 개선: O(N) → O(1) per 명령어
4️⃣ 명령어 처리 최적화: startswith()로 명령어 분기 단순화
5️⃣ 출력 최적화: "".join()으로 빠른 출력 처리

---

🎯 💡 최종 결론

• 단일 리스트의 중간 삽입/삭제는 시간 초과의 주요 원인
• 스택 2개 사용은 커서 위치 문제를 효율적으로 해결하는 핵심 전략
• 입력과 출력의 최적화는 대규모 입력 문제에서 반드시 고려해야 할 사항

🚀 → 이제 효율적이고 정확한 한 줄 에디터 풀이 완성! ✨✅