[자료구조] Python_Minimum Stack, Queue : O(1) 시간복잡도로 최솟값을 반환하는 함수를 구현하라.

Stack 알고리즘에서 O(1) 시간복잡도로 최솟값을 반환하는 방법

 

1. Stack 을 push 할 때, [원소 x, 현재까지 스택에 저장된 원소 중 최솟값] 저장하면 된다.

class minimum_Stack():
    def __init__(self):
        self.Stack = [] #파이썬은 리스트를 스택으로 사용가능
    def push(self, element): # 스택 push
        if not self.Stack:
            self.Stack.append([element, element])
        else: # 현재 스택의 최솟값(top.second)과 입력값을 비교하여 추가시킴.
            self.Stack.append([element, min(element, self.Stack[-1][1])])
    def pop(self):
        return self.Stack.pop() #스택 pop
    def pop_minimum(self):
        return self.Stack.pop()[1] #스택 pop - 최솟값 반환

st = minimum_Stack()
st.push(5)
st.push(4)
st.push(8)
print(st.pop_minimum())

단순히 원소 하나가 둘이 되었을 뿐이므로 추가와 삭제연산 모두 스택과 동일한 O(1) 상수 시간이다.

 

 

Queue 알고리즘에서 O(1) 시간복잡도로 최솟값을 반환하는 방법

 

1. 큐는 스택과 달리 FIFO(First In First Out, 선입선출) 구조라, 스택과 같은 방식은 불가능하다. 따라서, 양방향에서 데이터가 처리 할 수 있는 파이썬의 deque(double-ended queue) 자료구조를 사용하여 최솟값을 가장 끝에 담아놓게 한다.

from collections import deque
class minimum_Queue():
    def __init__(self):
        self.Queue = deque() #파이썬 collections.deque - 내부적으로 linked list를 사용함.
    def push(self, element): # 큐 push
        if not self.Queue:
            self.Queue.appendleft(element)
            self.Queue.append(element)
        else: # 현재 큐의 최솟값과 입력값을 비교하여 끝 인덱스에 추가시킴.
            min_value = self.Queue.pop()
            if min_value < element: #최소값 갱신
                self.Queue.append(element)
                self.Queue.append(min_value)
            else:
                self.Queue.append(element)
                self.Queue.append(element)
    def pop(self):
        return self.Queue.popleft() #큐 pop
    def pop_minimum(self):
        return self.Queue.pop() #큐 pop - 최솟값

q = minimum_Queue()
q.push(5)
q.push(4)
q.push(8)
print(q.pop_minimum())

Collections.deque 는 내부적으로 doubly linked list로 구현되어있어서, 시간복잡도를 확인해보면 앞 뒤에서 데이터를 처리하는 속도가 O(1) 이 된다.