[C++] LeetCode - Valid Parentheses (Stack)

그 유명한 괄호 열고 닫기 문제입니다. 열었을 때 스택에 추가하고, 닫았을 때 스택에서 제거하는 방식을 통해 정합성을 확인합니다.

Stack

• 스택은 LIFO를 따르는 자료 구조 (Last in First out)
• push: 스택의 끝에 값이 추가
• pop : 스택의 끝의 값을 날려버림.
• top : 스택의 끝의 값을 구함.
• stack<char> st; st.push('('); st.top(); st.pop(); 등으로 활용.

---

문제 정의

---

접근 방법

• 여는 괄호는 스택에 push, 닫는 괄호는 스택에 pop하되, top의 값의 괄호가 맞는지를 확인한다.

  실행 결과

  딱히 좋진 않지만 차이가 미미합니다. 얼마나 if문을 최대한 줄이고, false 조건일 때 빨리 리턴하느냐에 따라 다른 정도.
• Runtime: 3 ms, faster than 13.38% of C++ online submissions for Valid Parentheses.
• Memory Usage: 6.4 MB, less than 9.70% of C++ online submissions for Valid Parentheses.

  코드

  본인은 스택의 사이즈가 0인지를 비교하는 식으로 코드를 짰는데, 사실 stack.empty()를 활용하는 편이 더 깔끔하겠습니다.

---

class Solution {
public:
    bool isValid(string s) {
 
        stack<char> st;
        
        
        // use stack to check the sequence of each brackets
        for (int i=0; i<s.size(); i++) {
            if (s[i] == '(') {
                st.push(s[i]);
            } else if (s[i] == ')') {
                if (st.size() != 0 && st.top() == '(') {
                    st.pop();
                } else {
                    return false;
                }
            } else if (s[i] == '{') {
                st.push(s[i]);
            } else if (s[i] == '}') {
                if (st.size() != 0 && st.top() == '{') {
                    st.pop();
                } else {
                    return false;
                }
            } else if (s[i] == '[') {
                st.push(s[i]);
            } else if (s[i] == ']') {
                if (st.size() != 0 && st.top() == '[') {
                    st.pop();
                } else {
                    return false;
                }
            }
        }
 
    
        if (st.size() == 0) {
            return true;
        } else {
            return false;
        }
    }
};

---