🔎 문제

https://www.acmicpc.net/problem/1406
#스택

---

🔎 풀이

❌ [FAIL] 나의 첫번째 풀이

문자열을 리스트로 변환한 뒤, 커서 위치(index)를 따로 변수로 관리하며 삽입과 삭제를 리스트의 insert()와 del로 처리하였다.

strings = list(input())
n = int(input())
cursor = len(strings)

for i in range(n):
    order = input().split()

    if order[0] == "L" and cursor != 0:
        cursor -= 1
    elif order[0] == "D" and cursor != len(strings):
        cursor += 1
    elif order[0] == "B" and cursor != 0:
        del strings[cursor-1]
        cursor -= 1
    elif order[0] == "P":
        strings.insert(cursor, order[1])
        cursor += 1

strings = ''.join(strings)
print(strings)

🤔 결과 및 원인 분석

결과 : 시간초과

💥 원인 1: list.insert()와 del의 시간복잡도 = O(N)

strings.insert(cursor, order[1])
del strings[cursor-1]

이 두 연산은 리스트 중간에 삽입/삭제를 하기 때문에 O(N) 시간복잡도가 걸려요.
커서가 문자열 중간쯤일 때 매번 리스트를 밀고 당기게 되죠.

🤯 반복 횟수 N이 500,000이기 때문에 이게 시간 초과의 주 원인이 됩니다!

💥 원인 2: 입력시간 초과
백준에서는 기본적으로 sys.stdin.readline() 쓰는 걸 권장해요.
대신 이렇게 쓰면 \n이 남기 때문에 꼭 .strip() 붙여야 해요:

✅ 해결 방법: 스택 2개(리스트 2개)를 사용해서 O(1) 시간 복잡도로 바꿔야 해요
즉,

• 왼쪽 스택 left: 커서 왼쪽 문자들

• 오른쪽 스택 right: 커서 오른쪽 문자들

삽입, 삭제, 커서 이동 모두 .append()와 .pop()으로 처리 (O(1))

⭕️ [PASS] 풀이

import sys

left = list(sys.stdin.readline().strip())
right = []
n = int(sys.stdin.readline())

for i in range(n):
    order = sys.stdin.readline().split()

    if order[0] == "L" and left:
        right.append(left.pop())
    elif order[0] == "D" and right:
        left.append(right.pop())
    elif order[0] == "B" and left:
        left.pop()
    elif order[0] == "P":
        left.append(order[1])

right.reverse()
answer = left + right
print(''.join(answer))

L : left존재하는지 확인, left 마지막 pop, right에 append
D : right존재하는지 확인, right 마지막 pop, left에 append
B : left확인, left pop
P : left append

풀이 이미지 참고 링크

---

📚 배운 내용 : Python 문법

• 문자열의 특정 위치에 문자열 추가/삭제하는 방법
  슬라이싱을 이용해야한다.
  또는 list로 변환시켜서 list1.insert() 또는 del list1[0]로 구현해야 함.
• 리스트 → 문자열
  str()로 하면 될줄알았으나 그렇게하면 안됨! join()을 사용해서 변환가능함.

  # 리스트 -> 문자열 변환 예시
  strings = ''.join(strings)