23.04.10. 풀었던 문제들

Leetcode 20. Valid Parentheses

 stack을 사용할 줄만 안다면, 쉽게 구현할 수 있는 문제. 백준의 stack의 첫 문제였던 것으로 기억한다.

//  Runtime 0 ms Beats 100%
// Memory 6.2 MB Beats 81.54%

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(char c : s){
            if(c == '(' || c == '[' || c == '{') stk.push(c);
            else{
                if(stk.empty()) return false;
                if(c == ')'){
                    if(stk.top() == '(') stk.pop();
                    else return false;
                }
                else if(c == ']'){
                    if(stk.top() == '[') stk.pop();
                    else return false;
                }
                else if(c == '}'){
                    if(stk.top() == '{') stk.pop();
                    else return false;
                }
            }
        }
        return stk.empty();
    }
};

 

시간복잡도

 string의 모든 char를 순회하므로 O(n). stack의 push나 pop도 O(1)이다.

 

공간복잡도

 stack만 사용하는데, worst case stack은 string과 같은 size가 되므로 O(n)이다.