[Algorithm]해커랭크 - Queues: A Tale of Two Stacks

https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks/problem

Queue를 Stack 두개로 구현하는 문제이다.

처음 생각난 방법으로 구현했을 때 Time Out이 발생했고, 두번째 방법으로 풀었을때 성공을 했다.

방법 1

Push : 1. Push를 할 떄마다 Stack1의모든 원소를 순차적으로 꺼내 Stack2에 넣고 주어진 원소를 Stack1에 Push 한다.

   2. Stack2의 모든 원소를 순차적으로 꺼내어 Stack1에 Push 한다.

Pop : 1. Stack1은 이미 Queue 형태로 정렬되어 있기 때문에 Pop하면 된다. 

하지만 이 방법을 쓰면 모든 원소를 총 두번 이동시키므로 Push는 2N의 시간복잡도를 가지게 된다. 

그래서 2/3 정도의 Test Case가 Time Out이 발생했었다.

방법 2

내가 잘못 생각한 부분이, 항상 모든 원소가 하나의 Stack에 정렬되어 있어야 한다고 생각한 부분이다.

그래서 한번 Stack1 -> Stack2 로 값을 모두 이동시킨 후 새로운 값이 들어오면 모든 원소를 다시 정렬해야 되는데 어떻게 Time Out이 발생하지 않게 해결할 것인가 고민을 했었다.

당연하게도 나랑 똑같은 생각을 하고 있던 사람이 있었고, 그사람의 글을 보면서 Pop 명령은 Queue 형태로 정렬된 Stack2가 모두 Pop 되어 비어있을 경우에만 Stack1에서 Stack2로 모두 Push 하고 Stack2의 제일 위 원소를 빼내면 된다는 것을 깨달았다.

Push가 일어날 때에는 Stack1에 넣기만 하면 된다.

Linked List를 이용하면 간단하게 Queue를 구현할 수 있지만 왜 굳이 스택 두개를 이용해서 구현하냐는 의문이 들었는데, 이 문제는 그냥 이런 응용을 할 수 있는지 테스트 하는 알고리즘 문제니까 그런 것이라고 결론지었다.

방법 2를 구현한 코드

class MyQueue {
  
    public:
        stack<int> stack_newest_on_top, stack_oldest_on_top;   
        void push(int x) {
            stack_newest_on_top.push(x);
        }
 
        void pop() {
            if(stack_oldest_on_top.empty())
            {
                while(!stack_newest_on_top.empty())
                {
                    stack_oldest_on_top.push(stack_newest_on_top.top());
                    stack_newest_on_top.pop();
                }
            }
            stack_oldest_on_top.pop();
        }
 
        int front() {
            if(stack_oldest_on_top.empty())
            {
                while(!stack_newest_on_top.empty())
                {
                    stack_oldest_on_top.push(stack_newest_on_top.top());
                    stack_newest_on_top.pop();
                }
            }
            return stack_oldest_on_top.top();
        }
};

* 코드 작성 중 발생한 문제점

 항상 모든 원소가 하나의 Stack에 정렬되어 있어야 한다고 생각해서 문제를 해결하는 데 시간이 오래 걸렸다.