[백준 2024/02/10] 5397번 키로거

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

5397번: 키로거

 

1. 접근 방법

처음에 접근했던 방법은 index를 이용한 list였다.

 

아래 코드를 이용했고, 보기 좋게 '시간 초과' 를 당했다.. ㅜ

for i in range(int(input())):
    i = 0
    result = []
    for letter in input():
        if letter == '<':
            i -= 1
            if i < 0:
                i = 0
        elif letter == '>':
            i += 1
            if len(result) < i:
                i = len(result)
        elif letter == '-':
            if i > 0:
                del result[i-1]
                i -= 1
        else:
            result.insert(i, letter)
            i += 1

    print(''.join(result))

 

그래서 어떻게 접근할까 하다가 -> double linked list로 접근해야겠다고 생각했다. 

그 이유로는 list의 경우 한 값이 pop 되거나 insert할 경우 O(n) 의 시간 복잡도를 가지기 때문에 시간이 많이 소요되기  때문이다.

 

하지만, linked list의 경우 pop 과 insert에서 head부터 찾아서 pop이나 insert를 하지 않아도 될 경우, O(1)의 시간 복잡도를 지니기 때문이다. 

 

여기서 함수로 구현한 부분은 

__init__ : 설정 초기화

left : '<' 왼쪽 화살표일 경우

right : '>' 오른쪽 화살표일 경우

character : 문자가 입력되었을 경우

delete : '-' 가 입력되었을 경우

print : 마지막에 print하는 것

가 있다.

 

1) __init__

해당 경우에는 새로운 node를 만들고 그 값을 '~'으로 저장해주었다. 

왜냐하면, |abc와 같이 a 앞에 커서가 위치할 수 있기 때문이다. 그 경우엔, None을 가리킬 수 있기 때문에 '~'의 값을 넣어준 node를 처음에 만들어주었다.

None을 가리킬 경우 None.next 나 None.prev에서 error가 난다.

self.current는 현재 커서가 있는 위치를 나타내기 위해서 사용하였다.

 

2) left

왼쪽 화살표의 경우, current.data가 '~'인 경우엔, 맨 앞에 있는 것이기 때문에 return해주도록 하였다.

 

3) right

self.current.next가 None인 경우엔 맨 끝에 있는 것이기 때문에 return 해주도록 하였다.

 

4) character

character에서 많은 시행착오를 겪었다.

 

3가지 경우로 나누어서 character를 삽입할 수 있었다.

[1] 처음 값이 들어올 때,

[2] 맨 뒤에 문자를 넣는 경우

[3] 문자와 문자 사이에 값을 것는 경우

 

뭔가 복잡해진 것 같아서 마음에 크게 들진 않는다.

 

5) delete

current.data가 '~'인 경우, 맨 앞에 있는 것이기 때문에 지울 수 없다. 따라서 해당 경우 return을 해주었다.

 

self.current.next가 None이 아닐 경우엔, 삭제 되어야 하는 노드 앞 뒤로 값을 연결해주어야 하기 때문에 해당 경우도 고려해 주었다.

 

6) print

print의 경우, 처음에 선언한 '~' 노드를 제외한 다른 노드들을 하나씩 출력해주었다.

 

++ 다른 풀이들을 보아하니, 2개의 stack으로 푸는 것도 좋았을 듯 싶다. 

하지만, 이번 주차 문제 풀이가 linked list에 관한 것이어서 이를 이용해 보았다.

 

2. 코드

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoubleLinkedList:
    def __init__(self):
        new_node = Node('~')
        self.current = new_node
        self.head = new_node

    def left(self):
        if self.current.data == '~':
            return
        self.current = self.current.prev

    def right(self):
        if self.current.next is None:
            return
        self.current = self.current.next

    def character(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.current = new_node
            return

        if self.current.next is None:
            self.current.next = new_node
            new_node.prev = self.current
            self.current = new_node
            return

        new_node.prev = self.current
        new_node.next = self.current.next
        self.current.next.prev = new_node
        self.current.next = new_node
        self.current = self.current.next

    def delete(self):
        if self.current.data == '~':
            return
        if self.current.next is not None:
            self.current.next.prev = self.current.prev
        self.current.prev.next = self.current.next
        self.current = self.current.prev

    def print(self):
        self.head = self.head.next
        while self.head is not None:
            print(self.head.data,end="")
            self.head = self.head.next
        print()




for i in range(int(input())):
    keylog = DoubleLinkedList()
    for char in input():
        if char == '>':
          keylog.right()

        elif char == '<':
            keylog.left()

        elif char == '-':
            keylog.delete()
        else:
            keylog.character(char)

    keylog.print()