[백준 5397] 키로거 - Python

문제링크

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

5397번: 키로거

소스코드

import sys
sys.stdin = open("./input.txt", "r")
T = int(input())
 
for tc in range(1, T+1):
 
    #입력 문자열 저장
    L = list(sys.stdin.readline().replace("\n",""))
 
    #커서를 기준으로 왼쪽 범위 데이터, 오른쪽 범위 데이터를 담을 스택 각각 선언
    leftStack = []
    rightStack = []
 
    #문자열 순회
    for x in L:
 
        #'-'일때 왼족스택을 pop해 데이터 삭제
        if x == '-':
            if len(leftStack) != 0:
                leftStack.pop()
 
        #'<'일때 왼쪽스택의 top 데이터를 오른쪽 스택에 push
        elif x == '<':
            if len(leftStack) != 0:
                rightStack.append(leftStack.pop())
 
        #'>'일때 오른쪽스택의 top 데이터를 왼쪽 스택에 push
        elif x == '>':
            if len(rightStack) != 0:
                leftStack.append(rightStack.pop())
 
        #일반문자일때 왼쪽스택에 push
        else:
            leftStack.append(x)
 
    #스택리스트를 문자열로 전환
    left = ''.join(leftStack)
    right = ''.join(rightStack[::-1])
 
    #왼쪽문자열과 오른쪽문자열을 병합
    answer = ''.join([left,right])
 
    #결과출력
    print(answer)

 

문제접근

문제에서 비밀번호 입력 = 배열의 삽입

비밀번호 입력 위치 = 배열의 삽입 인덱스

 

직관적인 접근

1. 커서의 위치가 끝이면 배열의 마지막 인덱스에 데이터 삽입

2. 커서의 위치이동에 따라 인덱스를 옮겨서 데이터 삽입(삽입시 O(n)의 시간복잡도 소요)

 

문제점 - 시간초과

1. 입력데이터의 길이가 10만 이상일 경우 시간초과 발생(최악의 경우 거의 O(n^2)의 시간복잡도 소요)

 

해결 - 스택 사용

1. 배열을 두개로 분할하여 커서 기준 왼쪽에 위치한 데이터와 오른쪽에 위치한 데이터를 각각 담음

2. 커서의 이동에 따라 좌우 배열의 데이터를 이동함(데이터의 처음과 끝이 움직이기 때문에 O(1)의 시간복잡도 소요)

3. 입력데이터 처리가 종료되면 좌우 문자열을 하나로 합치고 출력