백준 5397 키로거

시간복잡도를 고려하지 않고, 이 문제를 해결하기 위해 단순하게 접근하는 방법은 아래와 같다.

커서를 두고 < 와 > 를 이동하면서 리스트에 문자열을 담아 처리하는 방법이다.

 

case = int(input());
 
for _ in range(case):
    s = list(input());
    cursor = 0;
    ret = [];
    for i in s:
        if i == '<':
            if cursor == 0: continue;
            cursor -= 1;
        elif i == '>':
            if cursor == len(ret): continue;
            cursor += 1;
        elif i == '-':
            if cursor == 0 : continue;
            ret.pop(cursor - 1);
            cursor -= 1;
        else:
            ret.insert(cursor,i);
            cursor += 1;
    for i in ret:
      print(i,end="");
    print("");

 

이 문제는 최대 입력이 100만 이기 때문에 시간복잡도를 고려하지 않으면 통과할 수가 없다.

list 의 경우 insert, delete, slice 등의 삭제 및 붙이는 부분이 O(n) 이다.

 

따라서 본인은  큐를 사용하는 방법으로 바꿨다.

이러면 대부분의 연산을 O(1)로 끝낼 수 있다.

또한 cursor를 없애고 두개의 큐를 이용해 커서를 통해 입력된 부분, 나중에 붙여줄 부분을 따로 저장 한 다음 출력하게 했다.

 

import sys;
from collections import deque;
case = int(input());
 
for _ in range(case):
  s = list(sys.stdin.readline().rstrip());
  cursor = 0;
  left = deque([]);
  right = deque([]);
  for i in s:
      if i == '<':
          if len(left) > 0:
            right.appendleft(left.pop());
      elif i == '>':
          if len(right) > 0:
            left.append(right.popleft());
      elif i == '-':
          if len(left) > 0:
            left.pop();
      else:
          left.append(i);
  while left:
    print(left.popleft(), end="");
  while right:
    print(right.popleft(), end="");
  print("");