[LeetCode] Min Stack

문제

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

 

예시

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

---

풀기

문제는 그냥 stack 구현하는 내용이다.

stack을 써도 되는건지 직접 다 구현하라는건가 했는데 좋은거 있는데 왜 안써? 마인드로 걍 씀.

---

결과

class MinStack() {
    private val stack = Stack<Int>()

    fun push(`val`: Int) {
        stack.push(`val`)
    }

    fun pop() {
        stack.pop()
    }

    fun top(): Int {
        return stack.peek()
    }

    fun getMin(): Int {
        return stack.min()
    }
}

 

위와 같이 풀었고 Accept 되었지만 GPT한테 이거 괜찮냐고 의견을 구해봄.

 

getMin 함수가 O(n) 복잡도를 가지니 더 최적화를 시켜 O(1) 복잡도로 변경시키자고 했음.

class MinStack() {
    private val stack = Stack<Int>()
    private val minStack = Stack<Int>() // 최소값을 저장하는 보조 스택

    fun push(`val`: Int) {
        stack.push(`val`)
        if (minStack.isEmpty() || `val` <= minStack.peek()) {
            minStack.push(`val`)
        }
    }

    fun pop() {
        if (stack.pop() == minStack.peek()) {
            minStack.pop() // 최소값이 사라지면 minStack에서도 제거
        }
    }

    fun top(): Int {
        return stack.peek()
    }

    fun getMin(): Int {
        return minStack.peek() // 최소값을 O(1) 시간에 반환
    }
}

 

위 코드가 GPT가 제안한 코드.

push 함수가 호출되면 minStack의 값을 확인해서 최솟값을 갱신.

pop 함수가 호출되면 그 값이 minStack 값과 비교해서 최솟값 삭제.

 

이렇게 하면 getMin 함수는 O(1) 복잡도가 된다.

 

GPT 짱~