[프로그래머스] 올바른 괄호

[프로그래머스] 고득점Kit 스택/큐 - 올바른 괄호

 

< 문제 > 

 

< 풀이 >

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

using namespace std;

bool solution(string s)
{
    bool answer = true;
    stack<char> bracket_string;

    for(int i=0; i< s.length(); i++)
    {
        bracket_string.push(s[i]);
    }
    
    int closeBracketCount =0;
    
    while(!bracket_string.empty())
    {
        if(bracket_string.top() == ')')
            closeBracketCount++;
        else if(bracket_string.top() == '(')
            closeBracketCount--;
        
        if(closeBracketCount == -1)
            return false;
        
        bracket_string.pop();
    }
    
    if(closeBracketCount != 0)
        return false;

    return answer;
}

 

< 해설 >

stack으로 뒷자리부터 문자열을 하나하나 검사하는 문제이다. 

핵심적인 요소로는 닫힘괄호 ' ) ' 없이 열림괄호 ' ( '  가 등장하면 바로 실패로 처리한다. 따라서 닫힘괄호를 만났을 때에는 closeBracketCount를 ++ 해주고 열림괄호가 등장하면 closeBracketCount-- 를 해주면 된다. while 문을 돌다가도 열림괄호의 수가 닫힘괄호보다 더 많아지면 바로 실패처리해준다.

이것만 해주면 몇 가지가 실패로 뜬다. 그 이유는 닫힘괄호만 있을때도 올바른 괄호가 성립하지 않기 때문.

)))) 또한 실패이므로 while문이 전부 다 돌았을 때 열림/닫힘 괄호의 개수가 동일한지(closeBracketCount가 0인지) 확인해주면 된다.