5397번 - 키로거

💡 커서는 연결리스트 or list or deque로 풀 수 있다.

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    
    answer = input().rstrip()
    left = []
    right = []
    
    for i in answer:
        
        if i == '<' and left:
            right.append(left.pop())
        elif i == '>' and right:
            left.append(right.pop())
        elif i == '-' and left:
            left.pop()
        elif 48 <= ord(i) <= 57 or 65 <= ord(i) <= 122:
            left.append(i)
    
    total = left + list(reversed(right))
    
    print(''.join(total))

• 이번 문제 같은 경우도 커서가 움직이면서 추가 and 삭제하는 문제였다.
• 이럴 경우에는 추가 와 삭제의 시간복잡도가 O(1)인 연결리스트 방식을 사용해서 풀어야한다.
• 파이썬의 경우에는 코딩테스트에서는 시간이 오래걸리는 Linked List를 직접 구현하는 경우가 잘 없기 떄문에, 대안 방책인 deque 와 List 중에서 list를 사용해서 구현하였다.
• 사용자로 부터 받는 입력을 하나씩 보면서 <가 나오면 left의 가장 마지막 부분을 right로 >가 나오면 right의 가장 마지막 부분을 left로 옮기도록 설정하였다. (맨 앞 or 맨 뒤 제외)
• list도 deque와 동일하므로 마지막에 뒤집어서 합쳐주었다.