[C++] 올바른 괄호

 

 

올바른 괄호

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

 

 

입출력 예

"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

 

 

스택의 성질을 사용하여 풀 수 있는 문제입니다. c++ 의 STL인 stack을 사용하였습니다. 문자열 s 의 문자를 하나씩 꺼내어  스택이 비어있다면 무조건 push, 스택의 맨위에 '('가 있을 때, 다음 괄호가 ')'라면 맨위의 '('를 pop, 아니라면 push.

 

이렇게 스택에 괄호를 모두 넣었을 때, 스택이 비어있다면 모든 괄호가 ( ) 인 쌍을 만족하고, 스택에 하나라도 남아있다면 false

 

 

 

풀이

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

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

 

 

 

[기초] 자료구조 / 스택(stack)