[백준] Linked list(연결 리스트) / 키로거

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

5397번: 키로거

 

문제 개요

비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램.

 

입력한 키: 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표

'-' : 백스페이스 (커서 바로 앞에 있는 글자를 지움(글자가 있으면))

‘<‘: 커서를 왼쪽으로 1만큼 움직임 (움직일 수 있다면)

‘>’: 커서를 오른쪽으로 1만큼 움직임 (움직일 수 있다면)

나머지 문자는 비밀번호의 일부. (나중에 백스페이스를 통해서 지울 수 있음)

 

 

Input

첫째 줄에 테스트 케이스의 개수

각 테스트 케이스는 한줄로 & 입력한 순서대로 길이가 L인 문자열 (input이 매우 큼 => 효율성이 중요함)

<<BP<A>>Cd-

 

Output

비밀번호를 출력한다. (비밀번호의 길이는 항상 0보다 크다.)

 

 

문제 풀이

class Node:
    def __init__(self, x):
        self.item = x
        self.before = None
        self.next = None

class LinkedList:
    def __init__(self) -> None:
        dummy = Node(-1)
        self.head = dummy
        self.cursor = self.head
    
    def append(self, x):
        new = Node(x)
        new.next = self.cursor.next
        new.before = self.cursor # type: ignore
        if self.cursor.next != None:
            self.cursor.next.before = new
        self.cursor.next = new # type: ignore
        self.cursor = new
        
    def delete(self):
        if self.cursor == self.head: return
        self.cursor.before.next = self.cursor.next
        if self.cursor.next != None:
            self.cursor.next.before = self.cursor.before
        self.cursor = self.cursor.before
    
    def left(self):
        if self.cursor == self.head: return
        self.cursor = self.cursor.before
        
    def right(self):
        if self.cursor.next == None: return
        self.cursor = self.cursor.next
        
    
L = int(input())
inputs = []
for _ in range(L):
    inputs.append(input())

for cmd in inputs:
    link_lst = LinkedList()
    answer = []
    for i in range(len(cmd)):
        if cmd[i] == "-":
            link_lst.delete()
        elif cmd[i] == "<":
            link_lst.left()
        elif cmd[i] == ">":
            link_lst.right()
        else:
            link_lst.append(cmd[i])

    crt = link_lst.head
    while crt.next != None:
        crt = crt.next
        answer.append(crt.item)
    
    print(''.join(answer))

=> cursor의 위치를 정확히 정의해야 함!