[LeetCode] 20. Valid Parentheses

문제 링크

leetcode: 20.Valid Parentheses

문제

• string s가 주어진다.
• s는 {,[,(,),],} 로 이루어졌다.
• 올바른 괄호쌍이 성립하는지 확인한다.
  • 열린 괄호는 맞는 쌍의 닫힌 괄호와 짝을이룬다.
  • 짝을 이루는 대응 순서가 일치해야 한다.

풀이

괄호 문제는 스택을 이용하는 문제의 주제로 자주 등장하는 것 같다.
스택 자체가 LIFO로 가장 나중에 등장한 값부터 확인하는 특징이 있고, 올바른 괄호 자체도 가장 나중에 등장한 괄호부터 처리하는 경우가 많기 때문인 것 같다.

• 주의할 점은 스택이 비어있을 때와 마지막에 비어있는지 확인하는 것이다.

• 그 외의 케이스는 열린 괄호라면 스택에 넣고 닫힌 괄호라면 스택의 첫번째 값과 대응되는지 확인한다.

코드

class Solution {
public:
    bool isValid(string s) {
        stack<char> SK;
        for(int i=0; i<s.size(); i++){
            if(SK.size()==0||\s[i]=='('||s[i]=='['||s[i]=='{') SK.push(s[i]);
            else{
                if(s[i]==')'&&SK.top()=='(') SK.pop();
                else if(s[i]=='}'&&SK.top()=='{') SK.pop();
                else if(s[i]==']'&&SK.top()=='[') SK.pop();
                else return false; 
            }
        }

        return SK.size()>0 ? false:true;
    }
};