파이썬 알고리즘 - 스택(Stack)에서 최소값 출력하기

개발자 면접 트레이딩 - 파이썬 알고리즘 문제(11)

 

(1). 개발자 면접 트레이닝 - 스택(Stack)에서 최소값 출력하기

① 스택(Stack) 구조 이해하는 것이 중요

② Push, Pop, Peek 개념 파악 후 아래 코드 실습

③ 스택은 개념 상 사용 하는 곳이 많다. (ex : 브라우저 뒤로가기 등)

④ 예를들어 [2, 3, 7, 9, 12]  의 최소값은 2 출력

 

 

(2). 소스 코드

PYTHON

#stack_min.py
import unittest

class stack():
    def __init__(self):
        self.items = []
        self.mins = []
        self.min = None

    def push(self, item):
        self.items.append(item)
        if self.min is not None:
            self.mins.append(self.min)
        if self.min is None or self.min > item:
            self.min = item

    def pop(self):
        self.items.pop()
        self.min = self.mins.pop()

    def getminimum(self):
        return self.min

    def peak(self):
        return self.items[-1]

class test(unittest.TestCase):
    def test(self):
        st = stack()
        st.push(5)
        self.assertEqual(5, st.getminimum())
        st.push(3)
        self.assertEqual(3, st.getminimum())
        self.assertEqual(3, st.peak())
        st.pop()
        self.assertEqual(5, st.getminimum())

unittest.main()

 

(3). 소스 코드 분석

① 7 라인 : 스택 클래스(Class) 선언

② 9 라인 :  mins, min 변수를 통해 현재 최소값, 최소값 배열 선언

③ 14 라인 : 스택 Push 메소드 선언

④ 22 라인 : 스택 Pop 메소드 선언

⑤ 27 라인 : 최소값 반환하는 getminimum 메소드 선언

⑥ 34 ~ 끝 : 스택에 데이터 삽입 후 assertEqula 단위 테스트 함수를 사용하여 최소값 확인 및 루트 데이터 비교

 

자료구조의 Stack(스택) 은 정말 중요한 개념이며, 응용 분야는 관련 검색을 통해 자세히 알아보자.

 

(4). 실행결과1 - 단위테스트 정상 출력(최소 값 결과 같을 경우)

 

 

(5). 실행결과2 - 단위테스트 에러 출력(최소 값 비교 다를 경우)