[실버 2] 백준 5397 - 키로거 (파이썬)

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

풀이

문자열 입력 중에 <, >, - 는 특별한 키로 작동한다.

1. < : 커서를 왼쪽으로 옮긴다.
2. : 커서를 오른쪽으로 옮긴다.
3. • : 커서 왼쪽의 문자를 삭제한다.

나머지 문자는 커서 위치에 삽입되며, 최종적으로 만들어진 문자열을 출력해야한다.

스택 2개를 활용하여 커서의 왼쪽과 오른쪽을 나누어 관리한다.

1. stack1 : 커서 왼쪽에 있는 문자들
2. stack2 : 커서 오른쪽에 있는 문자들

이 방식은 시간복잡도를 O(N)으로 유지하면서 빠르게 구현이 가능하다.

시간 복잡도 분석

• 각 테스트케이스마다 O(N)
• 전체 시간복잡도 : O(T * N)

코드

# 백준 5397 - 키로거
# 분류 : 자료구조

T = int(input())
for i in range(T) :
    S = input()
    
    stack1 = []
    stack2 = []
    for s in S :
        if s == "-" :
            if len(stack1) > 0 :
                stack1.pop(-1)
        elif s == "<" :
            if len(stack1) > 0 :
                stack2.append(stack1.pop(-1))
        elif s == ">" :
            if len(stack2) > 0 :
                stack1.append(stack2.pop(-1))
        else :
            stack1.append(s)
    print("".join(stack1) + "".join(stack2[::-1]))