[백준/BOJ] 5397번 : 키로거 _Python

5397번: 키로거

 

>문제

>접근방법

   (삽질ver) cursor 위치를 나타내는 변수로 새 리스트에 insert(cursor, pw[i]) 하기

    => list.insert의 시간복잡도때문에 시간초과가 뜬다.

   (제출ver) 리스트 두개를 만들고 사이에 커서를 둔다. <를 입력받으면 왼쪽 리스트의 끝 문자를 오른쪽 리스트에 append, >를 입력받으면 오른쪽 리스트의 끝 문자를 왼쪽 리스트에 append한다.

 

 

>풀이법

   1. 왼쪽과 오른쪽 두 개의 리스트를 만든다.

   2. 입력받은 문자열의 요소가 < 이면 왼쪽 리스트의 마지막 요소를 오른쪽 리스트에 append()한다.

   3. 입력받은 문자열의 요소가 > 이면 오른쪽 리스트의 마지막 요소를 왼쪽 리스트에 append()한다.

   4. 입력받은 문자열의 요소가 - 이면 왼쪽 리스트의 마지막 요소를 pop() 한다.

   5. 오른쪽 리스트는 역순으로 들어가있기 때문에 reverse시킨 후 왼쪽 리스트와 합친다.

 

   

>코드

(삽질ver)

ch = []
output = []
n = int(input())

for _ in range(n):

    cursor = 0
    del output[0:]
    del ch[0:]

    ch = list(input())

    for i in range(len(ch)):
        if ch[i] == '-' and cursor != 0:
            cursor -= 1
            del output[cursor]
        elif ch[i] == '<' and cursor != 0:
            cursor -= 1
        elif ch[i] == '>' and cursor < len(output):
            cursor += 1
        elif ch[i].isalpha() or ch[i].isdigit():
            output.insert(cursor, ch[i])
            cursor += 1
    
    for j in output:
        print(j, end='')
    print()

 

(제출ver)

n = int(input())

for _ in range(n):
    ch = list(input())
    l, r = [], []

    for i in ch:
        if i == '<':
            if l: #left가 공백이 아니면
                r.append(l.pop())
        elif i == '>':
            if r: #커서를 이동할 수 있으면
                l.append(r.pop())
        elif i == '-':
            if l: #삭제할 문자가 있으면
                l.pop()
        else:
            l.append(i)
    
    l.extend(reversed(r))

    print(''.join(l))

 

 

>결과

 

 

>결론 

시간초과 너무행