[알고리즘] 백준5397 키로거 - 파이썬

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

5397번: 키로거

 

 

[풀이 코드]

t = int(input())

for _ in range(t):
    l_list = []
    r_list = []
    data = input()
    for i in data:
        if i == '-':
            if l_list: #왼쪽 스택에 있을 경우
                l_list.pop()
        elif i == '<': # 왼스택에 있는 문자 오른쪽 스택으로
            if l_list:
                r_list.append(l_list.pop())
        elif i == '>': # 오스택에 있는 문자 왼쪽 스택으로
            if r_list:
                l_list.append(r_list.pop())
        else:
            l_list.append(i)
    l_list.extend(reversed(r_list)) # 오른쪽 스택에 있는 문자들은 뒤집어서 붙여야 한다.
    print(''.join(l_list))

• 문제 유형 : 스택, 그리디, 구현
• 처음 문제를 읽고 '<', '>' 이런 화살표의 경우에는 위치한 인덱스를 이동하고 그에 따라 문자도 옮겨주면 된다고 생각했지만 두 개의 스택을 선언해서 풀면 정말 쉽게 풀리는 문제였다.

 

[아이디어]

1.  기본적으로 문자는 입력되면 왼쪽 스택에 넣어준다.
2. 왼쪽 화살표 표시는 '<' 왼쪽 스택에 있는 문자를 오른쪽 스택에 옮겨준다. 반대로 오른쪽 화살표 표시는 '>' 오른쪽 스택에서 왼쪽 스택으로 옮겨준다.
3.  '-' 왼쪽 스택에서 문자를 삭제해준다.
4. 마지막으로 왼쪽 스택에 오른쪽 스택을 뒤집어서 붙여주면 된다.