어제는 스택으로 큐를 구현하는 문제였다면 오늘은 반대이다.
FIFO 구조를 가지는 큐로 LIFO 구조를 가지는 스택을 구현하는 문제이다.
첫 번째 아이디어
push 할 때는 그냥 넣고, pop 또는 top 할 때는 아래와 같은 절차를 수행한다.
- 기존에 큐에 있던 원소들을 한 개만 남기고 임시 큐에 넣는다.
- 기존 큐에 남은 한 개의 원소를 반환한다.
이렇게 할 경우 시간 복잡도는 push: O(1), pop/top: O(n) 이다. 공간 복잡도는 O(n) 이다.
첫 번째 아이디어 구현
from collections import deque
class MyStack:
def __init__(self):
self.queue = deque([])
def push(self, x: int) -> None:
self.queue.append(x)
def get_top_val(self):
temp_queue = deque([])
while len(self.queue) > 1:
temp_queue.append(self.queue.popleft())
ret_val = self.queue.popleft()
self.queue = temp_queue
return ret_val
def pop(self) -> int:
return self.get_top_val()
def top(self) -> int:
top_val = self.get_top_val()
self.queue.append(top_val)
return top_val
def empty(self) -> bool:
return len(self.queue) <= 0
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
이 구현은 임시 큐를 사용하여 기존 큐를 임시 큐로 대체하는 방법이다. 물론 임시 큐를 사용하지 않고 하나의 큐만 사용할 수도 있다.
from collections import deque
class MyStack:
def __init__(self):
self.queue = deque([])
self.items_changed = False
def _relocation_queue(self):
current_len = len(self.queue)
for _ in range(current_len - 1):
self.queue.append(self.queue.popleft())
def push(self, x: int) -> None:
self.queue.append(x)
self.items_changed = True
def pop(self) -> int:
if self.items_changed:
self._relocation_queue()
self.items_changed = True
return self.queue.popleft()
def top(self) -> int:
if self.items_changed:
self._relocation_queue()
self.items_changed = False
return self.queue[0]
def empty(self) -> bool:
return len(self.queue) <= 0
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
이 구현은 items_changed 라는 flag 변수를 이용하여 큐의 조성이 변경되었는지를 추적하고, pop 또는 top 연산 시 불필요한 재배치 연산을 하지 않도록 해 준다.
두 번째 아이디어
pop 또는 top 할 때는 그냥 빼고, push 할 때는 아래와 같은 절차를 수행한다.
- 큐에 넣고자 하는 값을 넣는다.
- 방금 넣은 값을 제외한 나머지를 빼고 다시 큐에 넣는다.
이렇게 할 경우 시간 복잡도는 push: O(n), pop/top: O(1) 이다. 공간 복잡도는 O(n) 이다.
두 번째 아이디어 구현
from collections import deque
class MyStack:
def __init__(self):
self.queue = deque([])
def push(self, x: int) -> None:
temp_queue = deque([x])
while self.queue:
temp_queue.append(self.queue.popleft())
self.queue = temp_queue
def pop(self) -> int:
return self.queue.popleft()
def top(self) -> int:
return self.queue[0]
def empty(self) -> bool:
return len(self.queue) <= 0
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
첫 번째 아이디어와 마찬가지로 큐의 재배치 연산을 push 에서도 수행할 수 있다. 또한 위와 같이 임시 큐를 사용하지 않고 한 개의 큐만을 사용하여 해결할 수도 있다.
from collections import deque
class MyStack:
def __init__(self):
self.queue = deque([])
def push(self, x: int) -> None:
self.queue.append(x)
current_len = len(self.queue)
for _ in range(current_len - 1):
self.queue.append(self.queue.popleft())
def pop(self) -> int:
return self.queue.popleft()
def top(self) -> int:
return self.queue[0]
def empty(self) -> bool:
return len(self.queue) <= 0
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
소감
일 주일 째 1일 1문제 풀이를 하고 있는데 습관 형성이 되는 것 같고 자존감에도 좋은 것 같다.
앞으로도 이렇게 습관을 들이는 것이 내 발전에도, 건강에도 도움이 될 것이라 생각한다.
