[코딩테스트] [프로그래머스] 올바른 괄호

문제

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

---

풀이

1. 여는 괄호 '('를 스택에 넣는다.

2. 닫는 괄호 ')'가 나온다면, 스택의 top에 여는 괄호가 있는지 검사한다.
   2-1. top이 여는 괄호라면, 쌍이므로 pop
   2-2. 여는 괄호가 아니라면, 닫는 괄호가 중복되었으므로 false를 반환

2-3. 스택이 비었다면 모두 쌍이 있다는 의미이기에 true 반환, 반대의 경우 false 반환

---

코드

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

using namespace std;

bool solution(string question)
{
    stack<char> st;
    for (char c : question)
    {
        if (c == '(')
        {
            st.push(c);
        }
        else if (c == ')')
        {
            if (st.empty())
            {
                return false;
            }
            else if (st.top() == '(')
            {
                st.pop();
            }
        }
    }
    
    if(st.empty())
    {
        return true;
    }
    else
    {
        return false;
    }
}

---

다른 풀이와 코드

0. 스택을 사용하지 않고, 여는 괄호와 닫는 괄호의 개수만으로 풀이한 코드이다.

1. 변수가 음수라면, 현재까지 문자열에 여는 괄호 없이 닫는 괄호만 있다는 뜻이기에 false를 반환한다.
   1-1. 아니라면, 문자열에 여는 괄호가 포함되어 있을 때 변수를 증가시키고, 닫는 괄호가 포함되어 있을 때 변수를 감소시킨다.

2. n이 0과 같은지 판단하는 조건식을 반환한다.

#include<string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    int n = 0;
    for (int i = 0; i < s.length(); i++) 
    {
        if (n < 0)
            return false;
            
        if (s[i] == '(')
            n++;
            
        else if (s[i] == ')')
            n--;
    }
    return n == 0;
}