[백준] 에디터(Python) - Stack

# 문제 

 

# 입출력 

 

# Idea

스택을 이용한 문제다. 이 문제의 특징은 주어진 시간제한이 매우 짧기 때문에, insert와 pop(i) 등을 사용해서는 시간복잡도가 커지기 때문에 사용할 수 없다. (시간초과가 뜬다) 그래서 pop()와 append()만을 이용해 스택으로 구현해야한다. 

그렇다면 이 문제를 어떻게 스택으로 구현하느냐? 필자는 처음에 각각의 L, D, B, P 경우를 하나하나 스택으로 구현할 수 있도록 경우를 생각했는데, 이럴 경우에 예외처리가 너무 복잡하고 까다로워져서 난항을 겪었다. 

따라서 이 문제의 핵심 아이디어는 커서의 위치를 기준으로 데이터를 두개의 스택으로 나누는 것이다! 처음에는 하나의 스택에 데이터를 모두 몰아넣는다. 그리고 앞서 언급한 pop과 append의 스택 연산을 이용해 상황에 맞게 원소를 넣고 빼는 것이다.
이러한 상황 중 커서를 왼쪽으로 이동하는 L 연산을 그림으로 나타내면 다음과 같다. 

 

 

# Code

"""
에디터
  - 스택으로 구현해보기 (선입후출) > pop(i)와 insert(i)가 아니라 pop()과 append(v)를 이용할 것 !
  - 커서를 중심으로 스택을 2개로 나눈다. 
"""

# 스택 2개로 시작 
st1 = list(input())
st2 = []
n = int(input())

for _ in range(n):
  com = input().split()

  if com[0] == 'L':
    if st1 :           # st1 비어있지 않으면 (예외처리 이렇게 간단하게 가능...)
      st2.append(st1.pop())
  
  elif com[0] == 'D':
    if st2:
      st1.append(st2.pop())

  elif com[0] == 'B':
    if st1:
      st1.pop()

  else:
    st1.append(com[1])

  print('st1 : ', st1)
  print('st2 : ', st2)

st1.extend(reversed(st2))    # 두 stack을 합쳐준다 
print(''.join(st1))