[백준] 5397 키로거

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

5397번: 키로거

이전 시도.

커서의 위치를 point변수로 설정하고 "<"나 ">"가 나오면 point를 1감소 1증가시켜 그 pointer에 해당하는 인덱스를 지웠다. 하지만 이 방식으로 하다보면 반례가 많고 시간복잡도가 매우 커, 양방향 대기열인 덱을 써보았다.

import sys
n = int(sys.stdin.readline())  # 입력받는 횟수
# 대문자, 소문자, 숫자, 백스페이스,화살표<>
password = [input() for _ in range(n)]  # 1차원 배열에 문자열 형식으로



for i in range(len(password)):
    a = (list(password[i]))
    stack = []
    point = 0
    for j in range(len(a)):
        
        if a[j] == "<":
            
            if point <= 0:
                point = 0

            else:
                point -=1

        elif a[j] == ">":
            if point >= (len(stack)):
                point =  len(stack)
            else:
                point += 1
        elif a[j] == "-":
            
            if len(stack) <= 0:
                point = 0
                stack.append("")
            else:   
                stack.pop(point-1)
                point-=1
        else:
            stack.insert(point,a[j])
            point += 1
            

    s = ""
    for k in range(0,len(stack)):
        s +=stack[k]
    print(s)

패스워드를 입력받을 횟수 n

n만큼 문자열을 입력 받아 password 리스트에 저장

password리스트의 각 원소들을 list()함수로 한문자씩 분리

커서 기준 왼쪽의 원소들을 저장하는 덱 dl,  커서 기준 오른쪽의 원소들을 저장하는 덱 dr

"<"이면 dl.pop & dr.appendleft()

">"이면 dr.popleft() & dl.append()

"-"이면 dl.pop()

숫자나 영문 소문자, 영문 대문자이면 dl.append()

from collections import deque

n = int(input())

password = []
for i in range(n):
    contain = input()
    password.append(contain)


for i in range(len(password)):
    dl = deque()
    dr = deque()
    word = list(password[i])
    for j in range(len(word)):
        if word[j] == "<":
            if len(dl) != 0:
                a = dl.pop()
                dr.appendleft(a)

        elif word[j] == ">":
            if len(dr) != 0:
                b = dr.popleft()
                dl.append(b)
        elif word[j] == "-":
            if len(dl) != 0:
                dl.pop()
        else:
            dl.append(word[j])
    

    
    print("".join(dl) + "".join(dr))

마지막으로 dl과 dr의 원소를 join함수를 이용해 출력을 한다.

이전에는 dr의 모든 원소를 dl에 append하여 join함수를 통해 출력을 하였는데, 만약 비밀번호의 길이가 무한정 길어질 경우 dr의 모든 원소를 하나하나 dl에 넣어주어야 하므로 시간초과가 발생한다. 

따라서 dl, dr 각각에서 join함수를 통해 하나의 문자열로 표현한 후 +연산자로 더해 주었다.