Level 2. 올바른 괄호

Level 2. 올바른 괄호

 

 

스택을 활용해 괄호 짝을 맞추었다.

 

스택이 비었거나 여는 괄호이면 스택에 넣는다.

 

스택에 뭐가 있는데 닫는 괄호이면 1개를 뺀다.

• 스택의 top은 항상 여는 괄호를 유지한다.
• push, pop 연산 후 top이 닫는 괄호면 즉시 false를 반환한다.

 

#include <iostream>
#include <stack>

using namespace std;

bool solution(string s)
{
    stack<char> stck;

    for (char c : s)
    {
        if (stck.empty() || c == '(')
            stck.emplace(c);
        else
            stck.pop();

        if (!stck.empty())
            if (stck.top() == ')')
                return false;
    }

    return stck.empty();
}

 

어차피 여는 괄호와 닫는 괄호 2가지 경우밖에 없고, 비었는지 여부만 확인하면 되기 때문에 스택을 사용할 필요 없이 int 변수 1개를 업-다운하며 사용해도 된다.

 

#include <iostream>

using namespace std;

bool solution(string s)
{
    int n = 0;

    for (char c : s)
    {
        if (c == '(')
            ++n;
        else if (c == ')')
            --n;

        if (n < 0)
            return false;
    }

    return n == 0;
}