[Easy] Leetcode | 20. Valid Parentheses | String, Stack

https://leetcode.com/problems/valid-parentheses/

- 문제
스택의 대표적인 문제인 괄호 검사 알고리즘 문제이다. 괄호로 이루어진 문자열이 주어지는데 이 문자열 속 괄호들이 쌍에 맞으며 순서 또한 맞는지 검사하는 문제이다. 

- 풀이
스택의 LIFO (Last In First Out) 성질을 이용하여 순서와 쌍을 검사한다. 대략적인 알고리즘은 문자열의 크기만큼 루프를 돌면서 열린 괄호는 모두 스택에 저장한다. 따라서 시간 복잡도는 O(n)이 될 것이며 최악의 경우 스택에 n개 모두 저장하므로 공간 복잡도는 O(n)이 될 것이다. 만약 닫힌 괄호( ')', '}', ']' ) 가 나온다면 무조건 스택의 top(마지막에 저장한 괄호)과 쌍이 맞아야 하므로 top이 쌍이 맞지 않다면 false를 반환하며 쌍이 맞다면 top의 요소를 pop한다. 이 과정을 반복하며 루프가 끝났을 때 스택이 비어있다면 true를 반환하고 스택에 요소가 남아있다면 쌍이 맞지 않아 pop되지 못했으므로 false를 반환한다. 다음은 소스 코드이다.

class Solution {
public:
    bool isValid(string s) {
        /*
            스택을 이용하여 문자열의 크기만큼 루프를 돕니다.
            루프를 돌면서 각 문자를 스택에 push합니다.
        */
        
        size_t sSize = s.size();
        if(sSize == 0) 
            return true;
        if((sSize & 1) == 1) 
            return false;
        
        stack<char> stk;
        for(size_t i = 0; i != sSize; ++i)
        {
            if(s[i] == '(' || s[i] == '{' || s[i] == '[')
            {
                stk.emplace(s[i]);
                continue;
            }
            else if(s[i] == ')')
            {
                if(stk.empty() || stk.top() != '(') 
                    return false;
                
                stk.pop();
                continue;
            }
            else if(s[i] == '}')
            {
                if(stk.empty() || stk.top() != '{') 
                    return false;
                
                stk.pop();
                continue;
            }
            else if(s[i] == ']')
            {
                if(stk.empty() || stk.top() != '[') 
                    return false;
                
                stk.pop();
                continue;
            }
        }
        
        return stk.empty();
    }
};

 
만약 요소가 object 타입이라면 emplace가 push보다 빠르다. char은 기본 타입이라 push나 emplace나 비슷.
주어진 문자열의 크기가 0이라면 true를 반환하고 홀수라면 무조건 짝이 안맞으므로 false를 반환한다.
만약 읽은 요소가 닫힌 괄호인데 스택에 저장된 요소가 없다면 짝이 맞지 않는 조건이므로 false를 반환한다.