23.04.13. 풀었던 문제들

Leetcode 946. Validate Stack Sequences

 programmers에서 풀어 본 stack simulation 문제이다. 2개의 vector가 주어지며 pushed vector 순서대로 숫자가 주어졌을 때  push를 자유롭게 한다. 이 때 popped vector 순서대로 숫자를 pop할 수 있는지 여부를 도출하는 문제다.

 

첫 접근

 처음 떠올린 아이디어는 다음과 같다.

• 모든 숫자가 0보다 크거나 같고 1000보다 작거나 같으므로 isPushed라는 flag를 하나 만든다. ... 1
• popped vector를 순회한다. 그 값(v라고 하자)이 unpushed인 경우, 그 수가 나올 때까지 stack에 push한다. ... 2
  • push 할 때, isPushed를 true로 마킹한다.
  • 그러면 stack top은 항상 v와 같다.
• v가 pushed인 경우 이미 stack에 들어간 적이 있는 것이다. stack top이 v와 같다면 해당 값을 pop한다. ... 3
• 그렇지 않다면 이미 pop해버린 것이므로 popped를 만들 수 없다. ... 4

// Runtime 7 ms Beats 85.57% 
// Memory 5.4 MB Beats 68.46% 

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int len = pushed.size();
        vector<bool> isPushed(len+1, false); // ... 1
        stack<int> stk;
        for(int i = 0, pushedidx = 0; i<len; i++){
            if(isPushed[popped[i]] == false){ // ... 2
                while(pushedidx < len){
                    stk.push(pushed[pushedidx]);
                    isPushed[pushed[pushedidx]] = true;
                    pushedidx++;
                    if(stk.top() == popped[i]) break;
                }
            }
            if(isPushed[popped[i]] == true && !stk.empty() && stk.top() == popped[i]){ // ... 3
                stk.pop();
            }
            else return false; // ... 4
        }
        return true;
    }
};

 

시간복잡도

 popped vector와 pushed vector를 1번 순회하기 때문에 O(n)

 

공간복잡도

 isPushed, stk 추가공간을 사용하며 둘 다 worst O(n) size를 가진다. 따라서 O(n)

 

 

두 번째 접근

 첫 접근은 popped vector를 순회했다. pushed vector를 순회하면서 좀 더 간단하게 문제를 풀 수 있다.

• pushed vector를 순회한다. pushed[i]를 v라고 하자.
• v를 stack에 넣는다. ... 1
• stack top이 popped[i]와 같으면 pop하고 i++해 준다. ... 2

 이렇게 하면 문제 조건을 그대로 구현하게 된다. pushed에 있는 값을 순서대로 push하고, popped[i]를 뺄 수 있을 때만 계속 뺀다. 그 결과로 stack이 비어 있어야 모든 popped vector element를 stack에서 pop한 것이므로, stack.empty() 여부가 정답이 된다.

// Runtime 7 ms Beats 85.57%
// Memory 15.3 MB Beats 86.87%

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;
        int i = 0;

        for(int v : pushed){
            stk.push(v); // ... 1
            while(!stk.empty() && stk.top() == popped[i]){ // ... 2
                stk.pop();
                i++;
            }
        }
        return stk.empty();
    }
};

 

시간복잡도

 pushed, popped, stack을 1번씩 순회하므로 O(n)이다.

 

공간복잡도

 stk만큼 추가 공간을 사용한다. worst case O(n).