[BOJ] #5397 - 키로거

5397번: 키로거

 

** 문제 유형

• 스택, 구현, 그리디

 

** 풀이

문자열의 크기가 최대 1,000,000이므로, 문제에서 요구하는 대로 구현하게 되면 문제를 해결할 수 없음
따라서 스택을 활용하여, 선형시간 안에 문제를 해결해야 함

 

1. 2개 만들고, 스택 2개의 중간 지점을 커서(cursor)로 간주 
2. 문자 입력시, 왼쪽 스택에 원소를 삽입
3. '-' 입력시, 왼쪽 스택에서 원소를 삭제
4. '<' 입력시, 왼쪽 스택에서 오른쪽 스택으로 원소 이동
5. '>' 입력시, 오른쪽 스택에서 왼쪽 스택으로 원소 이동
6. 출력시, 오른쪽 스택을 뒤집어서 출력

 

test_case = int(input())

for _ in range(test_case):
    data = input()
    left_stack = []
    right_stack = []

    for i in data:
        if i == '-':
            if left_stack: # 비어 있지 않으면
                left_stack.pop()
        elif i == '<':
            if left_stack: # 비어 있지 않으면
                right_stack.append(left_stack.pop())
        elif i == '>':
            if right_stack: # 비어 있지 않으면
                left_stack.append(right_stack.pop())
        else:
            left_stack.append(i)

    left_stack.extend(reversed(right_stack))
    print(''.join(left_stack))