* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *
leetcode 232번 ( https://leetcode.com/problems/implement-queue-using-stacks/ )
풀이방법 1.
교재를 보지 않고 시도했던 방법이다. 이전 문제와 비슷하게, 스택에서 사용할 수 있는 메소드만 사용해서 큐를 구현하는 문제이다.
이전의 큐는 원소를 빼낼 때는 앞에서, 원소를 넣을 때는 뒤에서 넣었다(FIFO). 반면 스택은 원소를 넣는 것과 빼는 작업이 모두 맨 뒤에서 일어난다(LIFO). 그래서 스택을 큐로 구현할 때처럼 큐의 앞에서 원소를 뺀 다음에 큐의 맨 뒤에 넣는 방식으로, 공간을 안 사용하고 풀 수는 없다. 스택에서 원소를 하나 빼서 하나를 다시 넣는다고 해서 스택의 값이 변하지 않기 때문이다.
그래서 스택 하나를 더 사용해서 정렬 작업을 할 것이다.
(여기서는 스택을 모두 리스트로 구현하였다.)
이제 push(), pop(), peek() 메소드를 구현해야 하는데, 어디서 정렬하는지는 상관없다. 이번 풀이에서는 push()할 때 정렬을 같이 진행했다.
기존 스택을 stack, 순서를 바꾸는 데 필요한 새 스택을 reverse로 두었다.
1. 새 값이 들어오면 먼저 기존 stacl에 있던 원소들을 전부 reverse로 옮긴다.
2. 빈 스택에 새 값을 먼저 넣은 뒤, reverse에 있던 값들을 다시 stack으로 옮기면 된다.
하노이 탑과 비슷한 원리이다.
push()에서 정렬 작업을 모두 마쳤기 때문에 pop(), peek() 메소드는 간단하게 구현할 수 있다.
peek()은 stack의 맨 마지막 원소를 리턴하면 되므로, 우선 원소가 있는지를 확인한 뒤 -1번째 인덱스를 리턴하면 된다.
(비어 있는 리스트에서 인덱스를 참조할 경우 오류가 나므로 주의하자)
pop()의 경우, 리스트에서 기본으로 제공되는 메소드이므로 그냥 사용하면 된다.
peek()과 마찬가지로 원소가 없는 리스트에서 pop()을 할 경우 오류가 발생하므로 길이를 확인한 뒤 실행하자.
전체 코드는 다음과 같다.
class MyQueue(object):
def __init__(self):
self.stack = []
self.reverse = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
for _ in range(len(self.stack)):
self.reverse.append(self.stack.pop())
self.stack.append(x)
for _ in range(len(self.reverse)):
self.stack.append(self.reverse.pop())
def pop(self):
"""
:rtype: int
"""
if len(self.stack) >= 1:
return self.stack.pop()
def peek(self):
"""
:rtype: int
"""
if len(self.stack) >= 1:
return self.stack[-1]
def empty(self):
"""
:rtype: bool
"""
return len(self.stack) == 0
풀이방법 2.
교재에서 언급된 풀이방법이다. 두 개의 스택(리스트로 구현)을 사용한다는 점은 같은데, 시공간 복잡도가 더 효율적이다.
이전 방법에서는 push()를 시행할 때마다 정렬을 진행하였는데, 이 경우 매번 stack에 있던 원소를 reverse로 옮긴 뒤, 새 원소를 넣고, 다시 reverse에서 stack으로 옮기면서 시간이 더 소요될 수 있다.
여기서도 두 개의 스택을 사용하지만 각 스택을 그때그때 들어오는 원소를 담아두는 input, peek()나 pop()이 호출될 때 스택을 정렬하기 위한 output으로 구분하였다.
즉 push()가 호출될 때마다 매번 정렬이 일어나지 않고, 정렬이 일어나더라도 모든 원소를 옮기지 않는 방식이다.
peek()나 pop()이 호출되면 우선 output 스택에 원소가 있는지 확인한다. 만약 원소가 있다면, 이 원소들은 input 스택에 들어있는 원소보다 이전에 들어온 원소들이 이미 정렬된 상태이므로, 여기서 가장 위에 있는 것을 제거한다.
만약 output 스택에 원소가 없다면, 그 때는 input 스택에 있던 원소를 output 스택으로 옮긴다. 이전 풀이에서의 하노이 탑과 같은 원리이기 때문에 input에서 가장 먼저 들어왔던 원소가 output 스택의 맨 위에 오게 된다.
이후 또 peek()나 pop()이 호출된다면, 그 때는 input 스택에 원소가 있던 없던 상관없이 output 스택의 맨 위에 가장 먼저 들어온 원소가 있으므로, output 스택이 빌 때까지 차례대로 빼서 사용하면 된다.
같은 원리이지만 불필요한 정렬을 줄인 방법이라고 볼 수 있겠다.
'알고리즘' 카테고리의 다른 글
| ch10-1-1(leetcode 641). 원형 데크 디자인(풀이X) (0) | 2023.01.12 |
|---|---|
| ch9-6(leetcode 622). 원형 큐 디자인 (2) | 2023.01.11 |
| ch9-4(leetcode 225). 큐를 이용한 스택 구현 (0) | 2023.01.11 |
| ch9-3(leetcode 739). 일일 온도 (0) | 2023.01.10 |
| ch9-2(leetcode 316). 중복 문자 제거 (0) | 2023.01.10 |