[백준] 1406번 (python 파이썬)

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

1406번: 에디터

 

import sys

s = sys.stdin.readline().strip()
order_number = int(sys.stdin.readline().strip())
cursor = len(s)  # 맨 앞을 0 이라고 정의한다. 
                 # 초기값으로는 주어진 문자열의 맨 뒤 len(s)값으로 한다.
for _ in range(order_number):
  order = sys.stdin.readline().strip()
  if order[0] == "L" and cursor:
    cursor = cursor-1
  elif order[0] == "D" and cursor < len(s):
    cursor = cursor+1
  elif order[0] == "B" and cursor and s:
      s = f'{s[:cursor-1]}{s[cursor:]}'
      cursor -= 1
  elif order[0] == "P":
    argument = order.split()[1]
    s = f'{s[:cursor]}{argument}{s[cursor:]}'
    cursor += len(argument)
print(s)

 

처음 생각한 대로 코드를 작성하니까 시간초과로 나온다.

문제에 문자열의 길이는 최대 10만, 명령어의 최대 개수는 50만 이라 한다.

최악의 경우엔, 10만길이의 문자열을 대상으로 50만개의 명령어를 수행하기 때문에 5백억개의 계산이 수행된다.

1초만에 실행하기엔 어림도 없을 뿐더러, 심지어 이 문제에서 시간제한은 0.3초이다.

 

구글링해서 다른 사람들 풀이를 봤다.

두 개의 스택을 이용해 푼 풀이였다.

 

현재 커서를 기준으로 서로 마주보는 스택 두개를 이용하는 개념이다.

문자열이 ABCD이고 커서가 B와 C 사이라고 한다면

 

        스택 1     cursor        스택2

[    "A",     "B"    ] ↔ [    "C",     "D"    ]

bottom         top     top           bottom

라는 구조라고 상상한다.

import sys

stack_left = list(sys.stdin.readline().strip())
stack_right = []
order_count = int(sys.stdin.readline().strip())
for _ in range(order_count):
  order = sys.stdin.readline().strip()
  if order[0] == "L" and stack_left:
    stack_right.append(stack_left.pop())
  elif order[0] == "D" and stack_right:
    stack_left.append(stack_right.pop())
  elif order[0] == "B" and stack_left:
    stack_left.pop()
  elif order[0] == "P":
    stack_left.append(order.split()[1])
stack_right.reverse()	# 오른쪽 스택은 좌우방향이 바뀌어야 한다
print("".join(stack_left+stack_right))

 

리스트의 append() 메서드와 pop() 메서드의 시간복잡도는 O(1)이다.

(최악의 경우) 명령을 50만번 수행하는 것을 바꿀순 없지만, 10만개 길이의 문자를 일일이 다루지 않아도 되므로 효율적이다.