3.5 스택정렬

문제 

가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성하라. 추가적으로 하나 정도의 스택은 사용해도 괜찮지만, 스택에 보관된 요소를 배열 등의 다른 자료구조로 복사할 수는 없다. 스택은 push, pop,peek,isEmpty의 네가지 연산을 제공해야한다. 

 

접근법

정렬을 위한 스택을 하나 더 사용한다고 했을떄, 두번째 스택에는 정렬된 형태로만 들어갈 수 있도록 하여 해당 값이 들어갈 위치를 찾아주는 방식으로 해결 할 수 있다. 

class SortStack :
    def __init__(self):
        stack = []

    def sort(self):
        tmp_stack = []
        while stack :
            cur_num = stack.pop()
            if not tmp_stack or tmp_stack[-1] > cur_num:
                while tmp_stack and tmp_stack[-1] > cur_num  :
                    stack.append(tmp_stack.pop())
            tmp_stack.append(cur_num)
        while tmp_stack :
            stack.append(tmp_stack.pop())