Stack : sort_stack 해설

 

👩‍💻 문제

The sort_stack function takes a single argument, a Stack object.  The function should sort the elements in the stack in ascending order (the lowest value will be at the top of the stack) using only one additional stack. 

The function should use the pop, push, peek, and is_empty methods of the Stack object.

 

작은 숫자가 맨 위에 오도록 정렬하라

 

💡 풀이

def sort_stack(stack):
    sorted_stack = Stack()
    while not stack.is_empty():
        temp = stack.pop()
        while not sorted_stack.is_empty() and sorted_stack.peek() > temp:
            stack.push(sorted_stack.pop())
         sorted_stack.push(temp)
    while not sorted_stack.is_empty():
        stack.push(sorted_stack.pop())

 

 

✍️ 해설

 

일단 기존 스택 vs 정리용 스택

정리용 스택은 내림차순으로 정렬하는거다 (4 3 2 1)

그리고 다시 원래 스택으로 되돌려 놓는 것 (1 2 3 4)

 

그러려면 기존 스택의 맨 위 값(temp)와 정리용스택의 top 값을 수시로 비교하면서

더 큰 값은 기존으로 돌려놓고,  작은 수는 정리용으로 쌓은 다음,

계속 temp와 top을 비교하는 것!! 

 

 

🥳 배운점

 

그림 그리면서 문제 푸는 법