[백준]5397 키로거 #stack

0. 기억해

실버3 이지만, stack을 생각하지못하면 풀 수 없는 문제임. 커서가 나오면 보통 스택을 쓴다고 하니 유념할것

​

1. 리스트 하나 (시간초과)

 (1) cursur변수를 따로두고, 리스트하나로 풀때.

 (2) insert와 del를 위해 리스트를 처음부터 끝까지 탐색해야하기 때문에 시간초과.

import sys

T=int(input())

for t in range(T):
    word = sys.stdin.readline().rstrip()
    size = len(word)
    cursur = 0
    nowWord=[]
    for i in range(size):
        if word[i]=="<":
            if cursur>0:
                cursur-=1
        elif word[i]==">":
            if cursur<len(nowWord):
                cursur+=1
        elif word[i]=="-":
            if cursur>0:
                del nowWord[cursur-1]
                cursur-=1
        else:
            if cursur==len(nowWord):
                nowWord.append(word[i])
            else:
                nowWord.insert(cursur,word[i])
            cursur+=1
        #print(nowWord,cursur)
    ans=""
    for i in nowWord:
        ans+=i
    print(ans)

 

2. 스택 2개 (통과)

(1) 커서이전의 문자(stack1)과 커서이후의 문자(stack2)를 이용하여 문제해결.

(2) 현재의 커서는 stack1의 가장 오른쪽에 있는걸로 생각한다. 아래의 3), 4)를 수행하면 커서가 보존됨

(이는 stack2의 가장 왼쪽이기도 함, 단 stack2는 오른쪽이 가장 최신문자이므로 엄밀히 말하면 가장 오른쪽)

(3) 왼쪽커서 ("<") : stack1의 문자를 stack2로 보냄.

(4) 오른쪽커서 (">") : stack2의 문자를 stack1로 보냄.

(5) 삭제 ("-") : stack1 pop()

(6) 추가 : stack1 append()

(7) 출력시 stack1은 왼쪽부터, stack2는 오른쪽부터 출력

from collections import deque

T=int(input())
for t in range(T):
    stack1=deque([])
    stack2=deque([])
    word=input()
    size=len(word)
    for i in range(size):
        c=word[i]
        if c=="<":
            if stack1:
                stack2.append(stack1.pop())
        elif c==">":
            if stack2:
                stack1.append(stack2.pop())
        elif c=="-":
            if stack1:
                stack1.pop()
        else:
            stack1.append(c)
    ans=""
    while(stack1):
        ans+=stack1.popleft()
    while(stack2):
        ans+=stack2.pop()
    print(ans)