[Stack] 백준 5397번 “키로거” Python 풀이

문제 링크

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

풀이

• 커서의 위치를 index = 0으로 둔 다음, 화살표에 따라 index를 변환하는 방식은 시간 복잡도가 높아 시간 초과가 발생합니다.
  • 문자열이 최대 길이는 1,000,000 이기 때문입니다.
• 따라서, 커서는 그대로 두고,
• 커서를 기준으로 왼쪽 문자열은 left라는 배열에, 오른쪽 문자열은 right라는 배열에 담는 방식으로 문제를 해결할 수 있습니다.
• 세부 알고리즘은 다음과 같습니다.
  1. 문자열이 들어오면 왼쪽 배열에 붙입니다.
  2. ‘>’ 가 들어오면 오른쪽 배열의 마지막 문자를 왼쪽 배열의 마지막에 붙입니다.
  3. ‘<’ 가 들어오면 왼쪽 배열의 마지막 문자를 오른쪽 배열의 마지막에 붙입니다.
  4. ‘-’ 가 들어오면 왼쪽 배열의 마지막 문자를 지웁니다.
• 단, 화살표와 지우기 버튼이 유효한 조건이 있습니다.
  • ‘>’ 는 오른쪽 배열의 마지막 문자를 왼쪽 배열의 마지막에 붙이는것이므로, 오른쪽 배열에 문자가 존재해야합니다.
  • ‘<’ 는 왼쪽 배열의 마지막 문자를 오른쪽 배열의 마지막에 붙이는것이므로, 왼쪽 배열에 문자가 존재해야합니다.
  • ‘-’ 는 왼쪽 배열의 마지막 문자를 지우는것이므로, 왼쪽 배열에 문자가 존재해야합니다.
• 그리고 마지막 출력은, 왼쪽 배열의 문자들을 공백없이 붙이고, 오른쪽 배열의 문자들을 reversed 해서 붙이면 됩니다.
  • 커서를 왼쪽으로 움직여서, 왼쪽 배열의 마지막 문자가 오른쪽 배열의 마지막에 추가되기 때문에,
  • 오른쪽 배열에는 실제 문자열의 정렬과 반대로 쌓이게 됩니다.
  • 예를 들어, abc (커서위치) def 라면, 왼쪽 배열에는 abc, 오른쪽 배열에는 fed 순으로 저장되게 됩니다.
• 추가적으로, ABC<<D>>E 를 예제로 사용해볼 수 있습니다.

코드

import sys

n = int(sys.stdin.readline())

for _ in range(n):

    left = []
    right = []

    pwd = list(sys.stdin.readline().rstrip())

    for char in pwd:

        if char == ">":
            if right:
                left.append(right.pop()) 

        elif char=="<":
            if left:
                right.append(left.pop())

        elif char=="-":
            if left:
                left.pop()

        else:
            left.append(char)

    print("".join(left) + "".join(reversed(right)))

참고

• https://chancoding.tistory.com/49
• https://assaeunji.github.io/python/2020-05-05-bj5397/
• https://esoongan.tistory.com/63