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

문제는 다음과 같습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

풀이 코드는 다음과 같습니다.

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

bool solution(string s)
{
    bool answer = true;
    stack<int>st;

    if(s[0]==')'||s[s.size()-1]=='(')
    {
        answer = false;
        return answer;
    }
    else
    {
        for(int i{0};i<s.size();i++)
        {
            if(s[i]==')')
            {
                if(st.empty())
                {
                    answer =false;
                    return answer;
                }
                else
                {
                    st.pop();
                }
            }
            else if(s[i]=='(')
            {
                st.push(1);
            }
        }
        
    }
    if(!st.empty())
    {
        answer=false;
    }

    return answer;
}

가장 기본적인 스텍(stack) 또는 큐(queue) 문제라고 생각됩니다.

짝을 맞추어야하는 부분을 간단하게 해결할 수 있기 때문입니다. 

stack에는 꼭 "(" , ")"를 넣을 필요 없이 코드처럼 숫자를 넣어도 무관합니다. 그 이유는 우리의 관심사는 "괄호가 올바르게 짝지어져있는가?"이기 때문에 stack에 뭘 넣었는지 관심없기 때문입니다.

여는 괄호 " ( " 를 받으면 stack에 하나를 추가하고 닫는 괄호 " ) " 를 받으면 stack에서 하나를 빼는 과정을 통해 문제를 해결 할 수 있고 처음부터 닫는 괄호 " ) "가 나오거나 맨 마지막에 여는 괄호 " ( "가 나오면 그 사이에 어떤 괄호가 나오든 짝이 맞지 않으므로 마로 false를 return 해줍니다.

같은 이유로 닫는 괄호 " ) "가 나왔는데 stack이 비어있으면 이미 올바르게 괄호가 지어지지 않았으므로 false를 출력하면 되며, 모든 문자열을 다 읽었는데 stack이 비어있지 않으면 여는 괄호 " ( "가 더 많다는 뜻이므로 false를 출력하면 됩니다.