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

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

널리 알려진 괄호 문제이다.
()() 이런 문자열은 올바른 괄호이고, (())) 이런 문자열은 잘못된 괄호이다.

문자열을 0부터 돌면서 ')'를 만나면 스택의 top을 확인하고 '('이라면 pop, 아니라면 push해주면 된다. (empty면 false를 리턴해주면 된다.)
'('라면 스택에 push해주면 된다.

스택의 크기가 문자열의 절반을 넘으면 더 이상 체크할 필요가 없이 잘못된 문자열이라 최적화 시도를 했는데, 결과엔 큰 차이가 없다. (아마도 테케에 그런게 없는 듯 하다)

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

using namespace std;


bool solution(string s)
{
    bool answer = true;
    
    stack<char> st;
    
    int idx = 0;
    while(1) {
        if(idx == s.size())
            break;
        //최적화 시도...
        if(st.size() > s.size() / 2) 
            break;
        char c = s[idx];
        if(c == ')') {
            if(st.empty())
                return false;
            if(st.top() == '(')
                st.pop();
            else 
                st.push(c);
        } else 
            st.push(c);
        idx++;
    }
    
    if(!st.empty())
        answer = false;
    
    return answer;
}

최적화 시도 안했을 때 결과

최적화 시도 했을 때 결과