[Python] 백준 5397번 - 키로거

📖 문제

5397번: 키로거

 

🔎 풀이

연결리스트 혹은 스택을 이용하여 푸는 문제입니다. 아래 코드는 스택을 활용하였습니다.

 

우선, 현재 위치를 기준으로 왼쪽과 오른쪽으로 나누어 글자를 담을 리스트를 생성해줍니다.

이후 커서의 위치가 이동할 때마다 리스트를 갱신해줍니다.

 

예를 들어, 커서가 오른쪽으로 움직이기 위해서는 오른쪽에 있는 글자를 왼쪽 리스트로 옮겨주어야 합니다. 이때 오른쪽 리스트에서는 첫번째 원소를 뽑아오게 되는데, 리스트는 pop(0)를 사용 시 O(n)의 비용이 필요하게 됩니다. 때문에 시간 비용을 줄이기 위해서 O(1)의 비용이 드는 pop()를 사용해야합니다.

 

해결 방안으로 오른쪽 리스트는 역순으로 저장하고, 마지막에 뒤집어서 왼쪽 리스트에 더해줍니다.

 

💻 코드

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    secret_order = input().strip()
    pre_stack = []
    post_stack = []
    
    # 화살표로 현재 위치가 옮겨질 때마다 현위치를 기준으로 앞쪽은 pre, 뒤쪽은 post에 저장
    # 이때 시간 비용을 줄이기 위해 post는 거꾸로 저장
    # 앞의 인덱스 원소를 제거 시 O(n), pop()을 이용할 시 O(1)
    for order in secret_order:
        if order == '-':
            if pre_stack: pre_stack.pop()

        elif order == '<':
            if pre_stack: post_stack.append(pre_stack.pop())

        elif order == '>':
            if post_stack : pre_stack.append(post_stack.pop())

        else:
            pre_stack.append(order)
    
    # pre_stack은 그대로, post_stack은 뒤집어서 합치기
    answer = ''.join(pre_stack) + ''.join(post_stack)[::-1]
    print(answer)