[백준] 1406번: 에디터 python

https://www.acmicpc.net/problem/1406

1406번: 에디터

 

 

눈물 줄줄 .. 

삽질에 삽질에 삽질에 삽질을 더해 성공 😭

 

문제 정보

스택

실버2

1h32m

x

설계 방법

나의 풀이

cursor의 범위를 0부터 len(str)까지로 잡고 if문을 활용하여 각 cmd 마다 상황에 맞게 해결

 

시간초과가 일어나지 않은 다른 풀이

1. sys.stdin.readline()을 쓰기 위해서 import sys.
2. 2개의 스택을 이용하여 커서가 움직일 때 마다 양 스택에 append or pop → remove, insert의 시간 복잡도 O(n)/ stack의 push, pop 시간복잡도 O(1)
3. 스택 왼쪽을 표현한 st1 변수에 문자 입력 받음
4. 스택 오른쪽을 표현한 st2 변수에 스택을 쌓기 위해 빈 리스트 초기화 후 시작
5. 커서가 왼쪽으로 움직이면 st2.append(st1.pop()), 커거가 오른쪽으로 움직이면 st1.append(st2.pop()) 이런식으로 구현

📍 주의. 마지막에 st1과 st2를 합칠 시 st2.reverse()로 하면 st2가 비어있을때 타입에러가 나기 때문에 reverse(st2)로 작성할 것

코드

내 코드

str = input()
n = int(input())
cursor = len(str)

for _ in range(n):
  cmd = input().split()
  if cmd[0] == "L" and cursor != 0:
    cursor -=1
  elif cmd[0] == "D" and cursor != n:
    cursor +=1
  elif cmd[0] == "B":
    # remove
    str = str[:cursor-1]+str[cursor:]
    cursor -= 1
  elif cmd[0] == "P":
    # insert
    str = str[:cursor]+ cmd[1] + str[cursor:]
    cursor += 1

print(str)

정답 코드

import sys

st1 = list(input())
st2 = []
n = int(input())
for _ in range(n):
  cmd = sys.stdin.readline().split()
  if cmd[0] == 'L':
    if st1:
      st2.append(st1.pop())
  elif cmd[0] == 'D':
    if st2:
      st1.append(st2.pop())
  elif cmd[0] == 'B':
    if st1:
      st1.pop()
  else:
    st1.append(cmd[1])
st1.extend(reversed(st2))
print(''.join(st1))

시간 복잡도

$O(1)$

어려웠던 점

시간제한이 0.3초로 굉장히 짧게 존재하였음 → sys import해와서 시도했지만 실패

sys 맨날 복사 붙어넣기만 하고 개념을 제대로 몰라서 헤맸음

참고 자료

[백준] 1406번 에디터 - 파이썬(Python)