Min Stack
일반적인 push, pop, top 외에도 getMin으로 스택에 들어 있는 가장 작은 값을 알려 줄 수 있는 스택을 설계하세요. 네 가지 연산은 각각 O(1) 시간에 실행되어야 합니다.
연산은 순서대로 ops에 주어지며, args[i]에는 push의 값이 들어 있고 그 외의 모든 연산에는 0이 들어 있습니다. 처음에 비어 있는 하나의 스택에 연산을 실행하고, 연산마다 문자열 하나를 반환하세요. push와 pop에는 "null"을, top과 getMin에는 숫자를 문자열로 반환하세요.
함수
- opsstring-array
- 연산이 실행되는 순서대로
- argsinteger-array
- 각 push의 값, 그 외 모든 연산에는 0
- 반환값string-array
- 연산당 하나의 답변, 텍스트로
제약 조건
1 ≤ ops.length ≤ 3000args.length == ops.length- 각
ops[i]는push,pop,top또는getMin입니다. -231+1 ≤ args[i] ≤ 231-1는 push의 경우이고, 다른 모든 연산의 경우에는args[i] == 0입니다.pop,top및getMin은 스택에 값이 하나 이상 있을 때만 호출됩니다.
예제
- 입력
- ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
- 출력
- ["null", "null", "null", "1", "null", "1", "null", "4"]
- 설명
- 스택에는 아래에서 위로 4, 1, 7이 있으므로 가장 작은 값은 1입니다. 7을 꺼내면 1이 맨 위에 남습니다. 1도 꺼내면 4만 남으므로 최솟값은 다시 4가 됩니다.
- 입력
- ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
- 출력
- ["null", "null", "null", "-2", "null", "-2", "null", "3"]
- 설명
- 최솟값인 -2가 두 번 푸시됩니다. 첫 번째 팝으로 하나가 제거되고 다른 하나는 여전히 남아 있으므로
getMin은 -2로 유지됩니다. 두 번째 팝을 한 뒤에야 최솟값이 3으로 돌아옵니다.
- 입력
- ops = ["push", "push", "pop", "push", "getMin", "top"]args = [2, 0, 0, 8, 0, 0]
- 출력
- ["null", "null", "null", "null", "2", "8"]
- 설명
- 0이 푸시되고 다시 팝되므로 더 이상 계산에 포함되지 않습니다. 그러면 스택에는 2와 8이 남습니다. 맨 위에는 8이 있고 최솟값은 2입니다.
제출 시 숨은 테스트 +16개
후속 질문
최솟값을 상각 O(1) 시간에 알려 주는 선입선출 큐를 만들 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
최솟값을 저장하는 변수 하나는 그 최솟값을 꺼낼 때까지는 잘 작동합니다. 그 순간 무엇을 알아야 하며, 그것을 언제 기록해 둘 수 있었을까요?
스택은 맨 위에서만 변경되므로, 어떤 높이 아래에 있는 값 중 최솟값은 그 높이가 채워져 있는 동안 그대로 유지됩니다. 값을 푸시할 때 최솟값을 기록하세요.
값 옆에 보조 스택을 둡니다. 새 값이 보조 스택의 맨 위 값보다 작거나 같으면 보조 스택에 넣고, 주 스택에서 꺼내는 값이 보조 스택의 맨 위 값과 같으면 보조 스택에서도 꺼냅니다. 그러면 보조 스택의 맨 위 값은 항상
getMin의 답이 됩니다.
풀이
일반적인 스택은 이미 push, pop, top을 O(1)에 수행합니다. 어려운 부분은 pop을 해도 유지되는 최솟값입니다. 핵심은 스택이 맨 위에서만 바뀐다는 점입니다. 어떤 높이에 값이 놓여 있는 동안 그 아래의 값은 바뀔 수 없으므로, 그 높이까지의 모든 값 중 최솟값은 고정됩니다. push할 때 그 최솟값을 기록해 두면 pop할 때 이전 최솟값을 별도 비용 없이 복원할 수 있습니다. 각 접근 방식은 무엇을 기록하는지에 따라 다릅니다.
getMin을 실행할 때마다 스택을 순회하세요
핵심 아이디어
push, pop, top에는 일반 스택을 사용하고, getMin을 호출할 때마다 스택에 들어 있는 모든 값을 살펴보고 가장 작은 값을 찾으면 됩니다. 호출 시점의 실제 내용을 확인하므로 항상 올바른 방법입니다.
하지만 O(1) 요구 사항을 충족하지 못합니다. 값이 n개인 스택에서 getMin을 호출하면 n개를 모두 읽습니다. 1,500개의 값을 푸시하고 매번 푸시 후 getMin을 호출하는 숨겨진 테스트에서는 약 1,500 × 1,500 / 2, 즉 백만 개가 넘는 값을 읽습니다. 반면 다른 접근 방식은 호출당 하나의 값만 읽습니다. 이러한 연산을 10^5번 실행하는 시스템이라면 수십억 개의 값을 읽게 됩니다.
최솟값 하나를 캐시에 저장하는 것으로는 해결되지 않습니다. 최솟값을 저장하는 변수는 푸시에는 효과가 있지만, 해당 값을 팝하고 나면 다시 스캔하지 않고는 다음으로 작은 값을 알 수 없습니다.
알고리즘
- 값을 스택으로 사용하는 목록에 저장합니다.
push x의 경우x를 추가하고,pop의 경우 마지막 값을 제거하며,top의 경우 마지막 값을 읽습니다.getMin의 경우 저장된 모든 값을 살펴보고 가장 작은 값을 반환합니다.- 각 답을 텍스트로 기록하고 목록을 반환합니다.
class MinStack:
def __init__(self):
self.values = []
def push(self, x):
self.values.append(x)
def pop(self):
self.values.pop()
def top(self):
return self.values[-1]
def getMin(self):
# Look at every stored value: O(n).
smallest = self.values[0]
for v in self.values:
if v < smallest:
smallest = v
return smallest
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result모든 값 옆에 최솟값을 저장하세요
핵심 아이디어
값이 스택의 높이 i에 있는 동안 그 아래의 값들은 바뀔 수 없으므로, 아래쪽 i개 값 중 최솟값은 해당 값이 그 자리에 있는 동안 고정됩니다. 각 값 옆에 그 숫자를 저장합니다. 즉, mins라는 두 번째 스택에서 mins[i]는 values[0..i]의 최솟값입니다.
push할 때 mins의 새 항목에는 x와 그 아래 항목 중 더 작은 값을 저장합니다. pop할 때는 두 스택 모두의 맨 위 항목을 제거합니다. 그러면 mins의 맨 위에는 남은 값들의 최솟값이 다시 놓이게 됩니다. getMin은 mins의 맨 위 값을 읽습니다.
첫 번째 예시에서 4, 1, 7을 push하면 최솟값 4, 1, 1이 저장됩니다. 7을 pop해도 mins의 맨 위에는 1이 남고, 1을 pop하면 4가 남습니다. 각 연산은 두 스택의 맨 위 항목만 다루므로 각각 O(1)입니다. 그 대가로 각 값마다 숫자를 하나 더 저장합니다.
알고리즘
- 높이가 같은 스택
values와mins를 유지합니다. push x의 경우,x를values에 넣고,x와mins의 맨 위 값 중 더 작은 값을mins에 넣습니다 (mins가 비어 있으면x자체를 넣습니다).pop의 경우 두 스택에서 모두 값을 꺼냅니다.top의 경우values의 맨 위 값을 읽고,getMin의 경우mins의 맨 위 값을 읽습니다.- 각 답을 텍스트로 기록하고 목록을 반환합니다.
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # mins[i] is the smallest of values[0..i]
def push(self, x):
self.values.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.values.pop()
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result새로운 최솟값이 나올 때만 늘어나는 최솟값 스택
핵심 아이디어
두 번째 접근 방식에서는 mins가 자주 같은 값을 반복합니다. 1을 넣고 이어서 7, 8, 9를 넣으면 mins에는 1, 1, 1, 1이 들어 있습니다. 반복된 항목은 새로운 정보를 알려 주지 않습니다. 따라서 값이 최솟값이 될 때만 mins에 기록하고, 그 값이 values에서 빠져나갈 때 제거합니다.
푸시할 때 mins가 비어 있거나 x가 맨 위 값 이하이면 x를 mins에 추가합니다. 팝할 때 values에서 빠져나가는 값이 mins의 맨 위 값과 같으면 mins도 팝합니다. mins의 맨 위 값은 항상 현재 최솟값입니다. 그 값이 추가된 후에 푸시된 모든 값은 더 크거나, 그 값 이하라서 역시 기록되었으며, 이후 팝되었기 때문입니다.
비교 연산자는 <가 아니라 <=여야 합니다. 두 번째 예시에서는 -2가 두 번 푸시됩니다. <를 사용하면 첫 번째 값만 기록되고, 첫 번째 팝에서 그 값이 mins에서 제거되어 -2가 아직 스택에 남아 있는데도 getMin은 3을 반환합니다. <=를 사용하면 각 값이 각각의 항목으로 기록됩니다.
네 가지 연산 모두 O(1)을 유지합니다. 값이 가장 큰 것부터 가장 작은 것 순서로 들어오면 mins는 values만큼 높아지고, 최솟값이 거의 바뀌지 않으면 짧게 유지됩니다.
알고리즘
values스택과mins스택을 유지합니다.push x의 경우x를values에 푸시합니다.mins가 비어 있거나x가mins의 맨 위 값보다 작거나 같으면x도mins에 푸시합니다.pop의 경우values에서 팝합니다. 제거된 값이mins의 맨 위 값과 같으면mins에서도 팝합니다.top의 경우values의 맨 위 값을 읽고,getMin의 경우mins의 맨 위 값을 읽습니다.- 각 답을 텍스트로 기록하고 목록을 반환합니다.
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # each value that was a minimum when pushed; the top is the current minimum
def push(self, x):
self.values.append(x)
# <= keeps one copy per equal minimum, so popping one leaves the others.
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
def pop(self):
if self.values.pop() == self.mins[-1]:
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result
함정과 경계 사례
여기서 다루는 버그는 최솟값의 중복 항목과 pop이 제거하는 항목에 관한 것입니다.
x가 엄격하게 더 작은 경우에만 새로운 최솟값을 기록합니다. 그러면 최솟값의 두 번째 복사본이mins에서 빠지고, 첫 번째 복사본을 꺼내면 두 번째 복사본이 여전히 스택에 있는데도 최솟값이 사라집니다. 두 번째 예시에서 이를 확인할 수 있습니다.- 최솟값을 변수 하나에 저장합니다. push는 처리하지만, 최솟값을 꺼낸 뒤에는 변수에 남은 값이 오래된 값이 되고, 다음으로 작은 값을 찾으려면 스캔해야 합니다.
- 박싱된 정수를 참조로 비교합니다. Java에서
Integer == Integer는 두 값이 같은 객체인지 묻습니다. Java가 캐시하는 -128부터 127까지의 값에서는 우연히 참이지만, 대부분의 더 큰 값에서는 거짓이므로 큰 값에서만 pop 검사가 실패합니다. Java 코드처럼 먼저int로 언박싱하세요. - 세 번째 접근 방식에서 pop을 할 때마다
mins를 꺼냅니다. 제거된 값이mins의 맨 위에 있을 때만 크기를 줄여야 합니다. 두 번째 접근 방식에서는 두 스택이 항상 함께 움직입니다. pop에서 숫자를 반환합니다. 이 형식에서pop은push처럼"null"을 반환합니다.
자주 묻는 질문4
O(1) 시간에 스택의 최솟값을 어떻게 구하나요?
푸시 시점의 최솟값을 기록하세요. 스택은 맨 위에서만 변경되므로, 어떤 높이 아래에 있는 값들의 최솟값은 그 높이가 채워져 있는 동안 변경될 수 없습니다. 각 높이의 최솟값을 저장하는 두 번째 스택을 유지하거나, 새로운 최솟값만 저장하면 getMin은 그 스택의 맨 위 값을 읽으면 됩니다.
값이 현재 최솟값과 같을 때 왜 최소 스택에 푸시하나요?
최솟값이 스택에 두 번 이상 있을 수 있기 때문입니다. 엄격히 더 작은 값만 기록하면 -2 두 개가 mins의 항목 하나를 공유합니다. -2를 처음 꺼낼 때 해당 항목이 제거되고, 두 번째 -2가 여전히 남아 있는데도 getMin은 이전 최솟값을 반환합니다. 같은 값도 기록하면 각 값마다 고유한 항목이 생깁니다.
Min Stack을 추가 공간 O(1)로 구현할 수 있나요?
스택 하나와 변수 min 하나로 가능합니다. 현재 최솟값보다 작은 x를 푸시할 때는 대신 2x - min을 저장하고 min = x로 설정합니다. 그러면 저장된 숫자가 min보다 작아져 표시 역할을 합니다. 표시된 숫자를 팝하면 이전 최솟값은 2 * min - stored입니다. 이 산술 연산은 한계값 근처에서 32비트 정수의 범위를 초과하므로 64비트 값이 필요하고, 부호 처리 로직은 오류가 발생하기 쉽습니다. 대부분의 면접관은 스택 두 개를 사용하는 방식을 선호합니다.
Min Stack의 시간 및 공간 복잡도는 무엇인가요?
모든 연산은 O(1)입니다. push, pop, top, getMin은 각각 하나 또는 두 개의 스택에서 맨 위만 읽거나 변경합니다. n개의 저장된 값에 필요한 공간은 O(n)입니다. 모든 값 옆에 최솟값을 저장하면 항상 2n개의 슬롯을 사용하고, 새로운 최솟값만 저장하면 n + 1개에서 2n개 사이의 슬롯을 사용합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def minStackOps(ops, args):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"] args = [4, 1, 7, 0, 0, 0, 0, 0]
기대값
["null", "null", "null", "1", "null", "1", "null", "4"]