5397. [Python]키로거

1. 문제

 

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

5397번: 키로거

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• 스택

 

3. 파이썬 코드

 

import sys
# 많은 인풋 처리
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    # 인풋값 공백 제거 후
    words = input().strip()
    # 왼쪽 리스트 오른쪽 리스트 생성
    left_list, right_list = [], []
    # 반복문을 진행하며
    for word in words:
        # 만약 < 움직임이면 left 리스트 값이 있으면 right 리스트에 값추가
        if word == "<":
            if left_list:
                right_list.append(left_list.pop())
        # 만약 > 움직임이면 right 리스트 값이 있으면 left 리스트에 값추가
        elif word == ">":
            if right_list:
                left_list.append(right_list.pop())
        # 만약 - 이면 left 리스트 값이 있으면 pop
        elif word == "-":
            if left_list:
                left_list.pop()
        # left 리스트에 값을 계속 추가
        else:
            left_list.append(word)
    # right 리스트 값이 없어질때 까지 뽑아서 왼쪽 리스트에 값추가
    while right_list:
        left_list.append(right_list.pop())
    
    print("".join(left_list))

 

4. 문제를 풀고난 후 생각

 

• 처음 시도했던 방식으로는

import sys

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    words = input()
    current_pos= 0
    ans = []
    for word in words:
        if word == "<":
            current_pos -= 1
            if current_pos < 0:
                current_pos = 0
        elif word == "-":
            if ans:
                ans.pop(current_pos-1)
                if current_pos == len(ans)+1:
                    current_pos -=1
        else:
            if word != ">":
                ans.insert(current_pos,word)
            current_pos += 1
            if current_pos >= len(ans):
                current_pos = len(ans)

    answer = "".join(ans)
    print(answer)

• 이런 방식으로 코드를 짰으며 커서가 나올때마다 current_pos 라는 변수를 통해서 현재 위치를 계속해서 찾아주는 방법을 선택했다. 하지만 insert를 사용하면 시간복잡도가 높아지기 때문에 다른 방식을 생각하는 도중 도저히 모르겠어서 인터넷 검색을 통해서 left_list 와 right_list 두개를 생성하여 접근하는 방식을 보고 구현해봤다.
• 내가 생각했던 insert 를 사용하는 것보다 pop 을 사용하면 시간복잡도가 훨씬 줄어들었고, 그에 따른 구현도 매우 간단해졌다. "<", ">" 경우만 리스트를 왼쪽 오른쪽 으로 이동시키면 끝났다.
• 이후 모든 값들은 왼쪽 리스트에서 계산을 시행했고, 끝나면 오른쪽 리스트의 값들을 모두 왼쪽에 추가해줬다. ( 아마 많아도 1개만 남아있을 것이다. 맨 마지막값 )

5. 문제를 푸는데 도움이 되는 지식

 

• 스택
• 자료구조