[프로그래머스 / Level_2 / C++] 올바른 괄호

스택을 잘 활용하면 풀 수 있는 쉬운 문제이다. 

 

#접근 방법 

 

괄호의 쌍은 '(' 와 ')' 이다. 

 

문자열의 길이만큼 돌아보면서 '(' 라면 스택에 담고 ')'라면 스택의 top에 '('가 위치한지 확인한다 

본인은 문자형으로 넣지 않고 숫자 1이 '(' 의 의미이다. 

 

만약 문자열의 현재 문자가 ')' 이고 stack의 top이 1이라면 ')'의 짝이 맞으니 스택의 top을 pop해준다. 

만약 문자열의 현재 문자가 ')' stack의 top이 1이 아니라면 ')' 괄호가 먼저 시작된 의미이므로 

더 돌아볼 필요도 없이 바로 false를 리턴해준다. 

 

그 이유는 괄호의 짝은 순차적으로 정해진다. 즉, ')' 닫히는 괄호를 만났다면 그 전에 짝인 '(' 괄호가 바로 앞에 존재해야한다. 

 

근데 '((((()))))" 이런식으로 되어있고 마지막 ')' 앞에 "))))" 4개나 있지 않나요?? 물어볼수 있다. 

 

반복문은 순차적으로 돌기 때문에 6번째 위치한 ')'를 볼때 앞에 '('와 함께 소거되기 때문에 스택은 차례대로 줄어든다. 

결국 stack의 top은 쌍이 맞아야만 소거되기 때문에 소거 되지 않는다면 그 즉시 이 괄호 문자열은 어긋난 것이라고 판단하면 된다. 

 

마지막에 또 스택의 크기를 체크한 이유는 애초에 "((((((" 이런 괄호가 온다면 스택에 집어 넣기만 한것이기 때문에 이것 또한 어긋날 괄호 문자열이라고 생각하면 된다.  

 

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

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

 

코딩테스트 연습 - 올바른 괄호