프로그래머스 - 올바른 괄호(Lv2)

이 문제를 첨에 재귀로 풀다가 도저히 못풀어서 인터넷 답을 봣다.

#include<string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    int p = 0,q = 0;
    for(int i = 0; i < s.size();i++)
    {
       if(s[i] =='(')
            p++;
        else
            p--;
        if(p < 0)
            break;
    }
    if((p) != 0)
        return false;
    return answer;
}

if(s[i] =='(')
p++;
else
p--;
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
if(p < 0)
break;
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
이부분에 있어서 이런 방식의 풀이를 암기 해놔야겠다.

다음의 풀이는 stack을 이용한 풀이이다.

#include<string>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

bool solution(string s)
{
   bool answer = true;
   stack<char> stk;
   
   for(int i = 0; i < s.size(); i++)
   {
       if(s[i] == '(')
           stk.push('(');
       else
       {
           if(!stk.empty() && stk.top() == '(')
               stk.pop();
           else
               stk.push(')');  
       }
   }
   if(stk.empty())
       return true;
   else
       return false;
}

두 방법 모두 풀이방법으로서 익혀두면 좋을 구조이다.