백준_python 5397번 키로거 (스택, 연결리스트(LinkedList))

<문제 링크>

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

 

 

<정답 코드>

 sol1 ) stack을 이용한 풀이

import sys
input = sys.stdin.readline
 
t = int(input())
 
for _ in range(t):
    str1 = []
    str2 = []
    for i in input().rstrip():
        if i == '-':
            if str1:
                str1.pop()
        elif i == '<':
            if str1:
                str2.append(str1.pop())
        elif i == '>':
            if str2:
                str1.append(str2.pop())
        else:
            str1.append(i)
    
    str1.extend(reversed(str2))
    print(''.join(str1))

 

커서를 기준으로 두 개의 스택(str1, str2) 사용

커서 왼쪽 문자들은 str1에, 커서 오른쪽 문자들은 str2에 역순(스택 특성)으로 저장

최종 결과는 str1과 str2를 조합해 완성

 

 sol 2 )  연결리스트(linked list)를 이용한 풀이

import sys
input = sys.stdin.readline
 
class Node:
    def __init__(self, data=None):
        self.data = data
        self.prev = None
        self.next = None
        
class LinkedList:
    def __init__(self):
        self.head = Node()          # 더미 헤드 노드
        self.cursor = self.head     # 커서는 헤드에 저장
 
    def insert(self, data):
        new_node = Node(data)
        new_node.prev = self.cursor
        new_node.next = self.cursor.next
 
        if self.cursor.next:
            self.cursor.next.prev = new_node
        
        self.cursor.next = new_node
        self.cursor = new_node
    
    def delete(self):
        if self.cursor is not self.head:    # 헤드에서는 삭제 불가
            self.cursor.prev.next = self.cursor.next
            if self.cursor.next:
                self.cursor.next.prev = self.cursor.prev
            self.cursor = self.cursor.prev  # 삭제 후 커서 왼쪽으로 이동
    
    def move_left(self):
        if self.cursor is not self.head:
            self.cursor = self.cursor.prev
 
    def move_right(self):
        if self.cursor.next:
            self.cursor = self.cursor.next
 
    def get_result(self):
        result = []
        current = self.head.next
 
        while current:
            result.append(current.data)
            current = current.next
 
        return ''.join(result)
 
def main():        
    t = int(input())
    for _ in range(t):
        linked_list = LinkedList()
        
        for c in input().rstrip():
            if c == '-':
                linked_list.delete()
            elif c == '<':
                linked_list.move_left()
            elif c == '>':
                linked_list.move_right()
            else:
                linked_list.insert(c)
        
        print(linked_list.get_result())
 
if __name__ == '__main__':
    main()

 

이중 연결 리스트 사용해 커서 위치 기준으로 노드 삽입 또는 삭제

커서 이동은 연결리스트의 prev와 next 포인터로 처리

 

 

< stack과 linked list 비교 >

stack	linked list
구현 단순 시간복잡도 O(1)로 빠름 적은 메모리 사용 커서 이동 많을 경우 두 스택 사이 이동 자주 발생해 비효율적 메모리 부족 발생 가능	커서 이동 시 O(1)로 빠름 동적 메모리 관리 특정 위치 연속 삽입/삭제 작업 효율 좋음 구현 복잡 스택에 비해 포인터 저장 위한 추가 메모리 사용 필요 cache hit rate 낮음