[백준 5397번] 키로거 - 파이썬

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

5397번: 키로거

 

💡문제 분석 요약

글자를 입력받고, <가 입력될 경우에는 커서를 왼쪽으로, >가 입력될 경우엔 커서를 오른쪽으로 이동하여 글자를 입력한다. -가 입력될 경우 커서 왼쪽의 글자를 삭제한다.

 

💡알고리즘 설계

스택과 연결리스트로 풀 수 있는 문제이다. 커서를 index로 두고, list.insert(index, c)로 해당 위치에 글자를 삽입하는 방법은 insert()의 시간복잡도가 O(N)이고, 문자열의 최대 길이가 백만이므로 시간초과가 된다.

(백만*백만은 1억이 넘으므로 1초가 초과됨)

 

스택을 이용한 풀이

1. 문자를 왼쪽 스택에 넣는다

2. <가 입력될 경우, 왼쪽 스택에 있는 마지막 문자를 오른쪽 스택에 넣는다.

3. >가 입력될 경우, 오른쪽 스택에 있는 마지막 문자를 왼쪽 스택에 넣는다.

4. -가 입력될 경우, 왼쪽 스택에 있는 마지막 문자를 pop한다.

 

마지막에 왼쪽 스택에 있는 문자열을 출력하고, 오른쪽 스택에 있는 문자열은 반대 순서로 출력한다.

<와 -는 왼쪽 스택에 문자가 있을 경우, >는 오른쪽 스택에 문자가 있을 때만 실행 가능하다.

 

<<BP<A>>Cd-가 입력될 경우,

1. < : 왼쪽 스택에 문자가 없으므로 넘어간다.

2. < : 왼쪽 스택에 문자가 없으므로 넘어간다.

3. [B] | []

4. [BP] | []

5. [B] | [P]

6. [BA] | [P]

7. [BAP] | []

8. > : 오른쪽 스택에 문자가 없으므로 넘어간다.

9. [ BAPC] | []

10. [BAPCd] | []

11. [BAPC] | []

출력 => BAPC

 

연결리스트 이용한 풀이

1. head와 tail에 빈 노드를 설정하고, 연결한다.

2. 현재 노드를 head로 설정한다.

3. <이 입력될 경우, 현재 노드가 head가 아니라면 이전 노드를 현재 노드로 설정한다.

4. >이 입력될 경우, 현재 노드가 tail가 아니라면 다음 노드를 현재 노드로 설정한다.

5. -이 입력될 경우, 현재 노드의 연결을 끊고 이전 노드를 현재 노드로 설정한다.

6. 문자가 입력될 경우, 새 노드를 만든 후 새 노드를 현재 노드와 다음 노드 사이에 삽입한 후, 현재 노드를 새 노드로 설정한다.

💡스택을 이용한 풀이 코드

import sys
input = sys.stdin.readline

T=int(input())
for _ in range(T):
    password=input().rstrip()
    stack1=[]
    stack2=[]
    for i in password:
        if i=='<':
            if stack1:
                stack2.append(stack1.pop())
        elif i=='>':
            if stack2:
                stack1.append(stack2.pop())
        elif i=='-':
            if stack1:
                stack1.pop()
        else:
            stack1.append(i)
    
    while stack2:
        stack1.append(stack2.pop())
    print(''.join(stack1))

 

💡연결리스트를 이용한 풀이 코드

import sys
input = sys.stdin.readline

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

def delete_node(node):
    global curr
    node.prev.next=node.next
    node.next.prev=node.prev
    curr = node.prev

def insert_node(node, data):
    global curr
    new_Node = Node(data)
    new_Node.prev=node
    new_Node.next=node.next
    
    node.next.prev=new_Node
    node.next = new_Node
    node=new_Node
    curr=node

T=int(input())
for _ in range(T):
    password=input().rstrip()

    head=Node('')
    tail=Node('')
    head.next=tail
    tail.prev=head

    curr=head
    for i in password:
        if i=='<':
            if curr!=head:
                curr=curr.prev

        elif i=='>':
            if curr.next!=tail:
                curr=curr.next

        elif i=='-':
            if curr!=head:
                delete_node(curr)

        else:
            insert_node(curr, i)
    
    node=head.next
    while node!=tail:
        print(node.data, end='')
        node=node.next
    print()

 

head와 tail의 빈 노드는 노드의 삽입과 삭제를 쉽게 하기 위해 설정했다.

연결리스트를 출력할 때, 다음 노드로 하나씩 이동하여 출력했다.

 

💡인덱스를 이용한 풀이 코드 (시간 초과)

import sys
input = sys.stdin.readline

T=int(input())
for _ in range(T):
    password=input().rstrip()
    l=[]
    idx=0
    len_password=len(password)
    for i in password:
        if i=='<':
            if idx!=0:
                idx-=1
        elif i=='>':
            if idx!=len_password:
                idx+=1
        elif i=='-':
            if l:
                l.pop()
        else:
            l.insert(idx, i)
            idx+=1
    
    print(''.join(l))

 

💡 느낀점 or 기억할 정보

 

차례로 위에서부터 배열을 이용한 풀이, 연결리스트를 이용한 풀이, 스택을 이용한 풀이이다.

이 문제를 파이썬으로 연결리스트를 이용해 구현한 풀이는 잘 없어서, c언어로 구현한 풀이를 참고하며 파이썬으로 구현했다.

delete_node에서 연결을 끊기만 하고 노드를 삭제하지는 않아서 메모리 관리가 잘 안된 것 같다.