[코딩 테스트] 스택/큐 > 20. Valid Parentheses

0. 링크

     LeetCode 문제 링크

1. 설명

    Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.
• Every close bracket has a corresponding open bracket of the same type.

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

입출력 예시

Input	Output
s = "()"	true
s = "()[]{}"	true
s = "(]"	false
s = "([])"	true

2. 해설

• 각 괄호는 서로 맞는 짝으로 열고 닫혀야한다. 이를 위해 스택을 사용한다.
• 다음을 S의 길이만큼 반복한다.

  • 스택이 비어있는 경우 : 여는 괄호는 스택에 넣고, 닫는 괄호는 return false;.
  • 스택이 빈 경우가 아니면 :
    • 닫는 괄호 : stack.top() 값과 비교한다. 현재의 char값이 같은 타입 (대, 중, 소)이고, 둘이 열고 닫는 조합이면 stack.pop()으로 스택의 값을 뺀다.
    • 여는 괄호 : 스택에 넣는다.

• 최종적으로 스택이 비어있다면 return true;, 아니라면 return false;.
  • 스택에 값이 남아있다는 뜻은 짝을 찾지 못한 괄호가 있다는 뜻. 입출력 #3을 참고.

3. 코드

#include <vector>
#include <stack>

class Solution {
public:
    bool isValid(string s)
    {
        vector<char> arr;
        stack<char> bracket;

        for(char c : s)
        {
            if(bracket.empty())
            {
                if(c == ')' || c == ']' || c == '}')
                    return false;
                else
                    bracket.push(c);
                
            }
            else
            {
                char top = bracket.top();
                if (c == '(' || c == '{' || c == '[')
                    bracket.push(c);
                else
                {
                    switch(top)
                    {
                        case '(':
                        {
                            if (c == ')')
                                bracket.pop();
                            else
                                return false;
                            break;
                        }
                        case '{':
                        {
                            if (c == '}')
                                bracket.pop();
                            else
                                return false;
                            break;
                        }
                        case '[':
                        {
                            if (c == ']')
                                bracket.pop();
                            else
                                return false;
                            break;
                        }
                    }
                }
            }
        }
        if(bracket.empty())
			return true;
        else
            return false;

    }
};

4. 감상

     스택을 사용하여 푸는 문제였다만, 어떤 부분에 스택을 사용하여 푸는지 감을 잡지 못했었다. 함수 호출 스택을 기억에서 떠올렸더라면 금방 감을 잡았을 것 같았다. 스터디 팀원의 설명을 들으니 금방 이해할 수 있었다.