백준 5397번 파이썬 _ 키로거 (실버3)

www.acmicpc.net/problem/5397

5397번: 키로거

문제유형 : 스택, 리스트, 구현 

 

문제풀이 :

 

커서의 위치를 0으로 두고 앞뒤로 움직일때마다 커서도 움직이는 형태로 진행하면 구현은 되나 시간복잡도가 높아져서 시간초과가난다.

처음에나도 이런 방식으로 코딩하고 구현은 됬는데 시간초과가 나서 실패함

 

사실 조금만 생각해봐도 테스트의 길이가 최대 1,000,000이므로 커서위치를 구해서 커서위치에서 지우거나 삽입할때 시간이 오래걸리게된다 . (pop(커서위치) 이런식으로 커서가 위치한곳에서 pop하거나 insert해야하므로 시간초과가 여기서 남)

 

문자열을 그대로 두고 커서움직임 (일반적 생각) -> 시간초과로 문제해결이 되지 않는다 -> 발상의 전환이 필요함

 

커서는 움직이지않고 커서를 기준으로 왼쪽은 left라는 배열에 , 오른쪽은 right라는 배열에 담아 배열2개를 활용하면 문제해결이 가능하다.

 

Case구분

1. 커서를 왼쪽으로 움직이는경우 : 왼쪽의 마지막 원소를 오른쪽리스트에 추가

2. 커서를 오른쪽으로 움직이는 경우 : 오른쪽 마지막 원소를 왼쪽리스트에 추가

3. 문자가 추가되는경우 : 왼쪽리스트에 추가 (스택처럼 쌓임)

4. 문자가 삭제되는경우 : 왼쪽리스트의 마지막원소를 제거

 

단 주의할점은 커서를 왼쪽으로 움직여서 오른쪽리스트가 추가될때 스택형식으로 쌓이므로 오른쪽 리스트에는 실제 문자열의 정렬과 반대로 정렬되어 쌓인다. 

예를들어 abc(커서위치)def 이면 왼쪽리스트에는 abc, 오른쪽리스트에는 fed순으로 저장되있음.

 

정답코드 :

import sys
input = sys.stdin.readline

n = int(input())

for i in range(n):
    password = list(input().strip())
    left, right = [], []

    for j in password:
        if j == '<':
            if left:  // left가 비어있지 않으면 -> 커서가 이동가능하면 
                right.append(left.pop())
        elif j == '>':
            if right:  // 커서가 이동가능하면 
                left.append(right.pop())
        elif j == '-':
            if left:  // 삭제할 문제가 있으면 
                left.pop()
        else:
            left.append(j)

    left.extend(reversed(right)) // right배열은 실제 문자열과 반대정렬이므로 다시 원래대로돌림 

    print(''.join(left))

 

시간초과 났던 코드 :

import sys
input = sys.stdin.readline

n = int(input())

for i in range(n):
    password = list(input().strip())
    answer = []
    curr = 0

    for j in password:
        if j == '<' and curr > 0: #글자가 있어서 커서를 움직일 수 있는경우
            curr -= 1 # 커서위치를 앞으로 하나 땡긴다
        elif j == '>' and curr < len(answer): #커서가 맨끝이 아닌경우
            curr += 1
        elif j == '-' and curr > 0: # 현재 커서앞에 문자가 있어서 지울문자가 있는경우 -> 커서가 0이상이면 문자가 있으므로
            answer.pop(curr-1)
            curr -= 1
        elif j != '<' and j != '>' and j!= '-':
            answer.insert(curr, j)
            curr += 1

    print(''.join(answer))