[알고리즘/프로그래머스] 올바른 괄호 C++

괄호로 이루어진 문자열이 들어온다.

스택을 이용해서 괄호를 확인해주면 된다.

 

'('이 나온경우 스택에 넣고 ')'이 나오면 스택에 있던 '('을 빼주면 된다.

스택에 뺄'('가 없는데 ')'이 먼저 들어오는 경우도 잘못된 경우이며,

이제 문자열 확인이 끝났는데 스택에 '('이 남아있는 경우도 잘못된 경우이다.

 

여기서 스택을 직접 사용할 필요는 없고 괄호 카운팅용 정수 변수를 사용해서 구현한다.

 

#include<string>
#include <iostream>
using namespace std;

bool solution(string s)
{
    bool answer = true;
    int cnt = 0;
    
    for(auto el : s){
        if(el == '('){
            cnt++;
        }else{
            cnt--;
        }
        if(cnt<0){
            return false;
        }
    }
    
    if(cnt==0){
        answer=true;
    }else{
        answer=false;
    }

    return answer;
}

카운터를 0으로 초기화하고,

 

'('인 경우 +1

')'인 경우 -1

그리고 카운터가 음수로 변하면 ')'가 먼저 나온게 되므로 false를 반환한다.

 

문자열 전체 순회가 끝나고

카운터가 0이 아니라면 '('이 더 많은 것이므로 false

 

카운터가 0인 경우 true를 반환한다.