[ds] 백준 #5397 키로거

문제

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

풀이

1. list 1개

n = int(input()) #testcase number
testcase = []
for _ in range(n):
  testcase.append(input())
# lisf의 마지막 칸을 표시하기 위한 '/'
password = [['/']for _ in testcase]
print(password)

for i, L in zip(range(n), testcase):
  cursor = -1
  for s in L:
    if s=='<':
      if cursor>=0:
        cursor -= 1
    elif s=='>':
      if password[i][cursor+1] != '/':
        cursor += 1
    elif s=='-':
      if cursor>=0:
        del password[i][cursor]
        cursor -= 1
    else:
      cursor += 1
      password[i].insert(cursor, s)
      
for i in password:
  print(''.join(i[:-1]))

결과는 시간초과

2. list 2개

n = int(input())
testcase = []
for _ in range(n):
  testcase.append(input())

for L in testcase:
  stack1, stack2 = [], []
  for s in L:
    if s == '<':
      if stack1:
        stack2.append(stack1.pop())
    elif s == '>':
      if stack2:
        stack1.append(stack2.pop())
    elif s == '-':
      if stack1:
        stack1.pop()
    else:
      stack1.append(s)
  print(''.join(stack1)+''.join(reversed(stack2)))

접근

리스트 하나로 했을 때 시간초과가 떠서 커서를 중심으로 리스트를 두 개로 나눔.
처음에 리스트 하나로 할 때는 커서의 위치를 옮겼었는데 리스트 두 개로 할 때는
커서는 가만히 놔두고 커서를 중심으로 문자를 옮김.
리스트 두 개는 stack으로 해서 문자를 옮기기 편하게 함.
커서 오른쪽 stack은 마지막에 뒤집어서 합쳐줌.