코딩 테스트 연습 - MinStack

01. 이해

입력받은 명령에 대해 기대되는 결과를 반환하는 함수를 포함한 커스텀 스택 클래스 작성

02. 계획

스택 클래스를 손으로 만들어 본다고 생각하면 될듯.

03. 실행

class MinStack() {

    /** initialize your data structure here. */
    private val stack = ArrayList<Int>()

    fun push(x: Int) {
        stack.add(x)
    }

    fun pop() {
        stack.removeAt(stack.lastIndex)
    }

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

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

}


class MinStack2() {

    data class Node(val value : Int, val min : Int)

    /** initialize your data structure here. */
    private val stack = ArrayList<Node>()

    fun push(x: Int) {
        if (stack.isEmpty()){
            stack.add(Node(x, x))
        } else {
            if (x < stack.last().min){
                stack.add(Node(x, x))
            } else {
                stack.add(Node(x, stack.last().min))
            }

        }
    }

    fun pop() {
        stack.removeAt(stack.lastIndex)
    }

    fun top(): Int {
        return stack.last().value
    }

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

}

04. 회고

처음 제출한 답안은 속도랑 메모리가 너무 좋지 않게 나와서 개선을 위해 구글링을 해 봤다.
다른 함수의 경우 기존의 함수를 바로 사용하기만 하는 거라 개선의 여지를 찾기 힘들었지만 'getMin'의 경우 탐색을 통해 최소값을 찾는 것이 아닌 'push'를 통해 값을 넣을 때마다 그 시점의 최소값을 저장해 놓는 것으로 개선점을 찾을 수 있었다.