[LeetCode] 20. Valid Parentheses 문제 풀이 C++

#INFO

난이도 : Easy

알고리즘 : Stack

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

Valid Parentheses - LeetCode

---

#SOLVE

스택 자료구조를 활용하면 간단하게 풀이할 수 있는 문제이다.

문자열 s 가 매개변수로 주어지며, s는 '(' , ')' , '{' , '}' , '[', ']' 문자 만을 포함한다.

여는 괄호는 반드시 그에 맞는 닫는 괄호와 짝을 이루어야 한다. 예를 들어 ' ( ' 는 ' ) ' 과 ' [ ' 는 ' ] ' 과 짝을 이룬다.

왼쪽 괄호 " ( { [ " 가 들어왔을 경우 스택에 푸시한다.

오른쪽 괄호 " ) } ] " 가 들어왔을 경우에는 우선 스택이 비어있지는 않은지 확인하고, 가장 위의 스택이 짝을 이루는 괄호라면 스택에서 pop 한다.

앞서 설명한 알고리즘을 코드로 표현하면 다음과 같다.

        stack<char> stk;
        for(const auto& i : s){
            if(!stk.empty() && (i == ')' || i == ']' || i == '}')){
                if(i == ')' && stk.top() == '(') stk.pop();
                else if(i == ']' && stk.top() == '[') stk.pop();
                else if(i == '}' && stk.top() == '{') stk.pop();
                else stk.push(i);
            }
            else{
                stk.push(i);
            }
        }

 

만약 스택에 문자가 남아있다면 쌍을 이루는 괄호 문자열이 아니기에 false를 리턴하고 스택이 비어있다면 쌍을 이루는 괄호 문자열 이라는 뜻 이기에 true를 리턴한다.

        if(stk.empty()) return true;
        else return false;

---

#CODE

class Solution {
public:
    bool isValid(string_view s) {
        stack<char> stk;
        for(const auto& i : s){
            if(!stk.empty() && (i == ')' || i == ']' || i == '}')){
                if(i == ')' && stk.top() == '(') stk.pop();
                else if(i == ']' && stk.top() == '[') stk.pop();
                else if(i == '}' && stk.top() == '{') stk.pop();
                else stk.push(i);
            }
            else{
                stk.push(i);
            }
        }
        if(stk.empty()) return true;
        else return false;
    }
};