[c++][프로그래머스] 올바른 괄호

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

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

괄호가 올바르게 짝지어졌다는 것은 스택으로 계산할 수 있습니다. '(' 와 ')' 가 붙어있다면, 제거할 수 있습니다.(전에 풀었던 문제와 비슷합니다) 

 

1. 가장 먼저 스택이 비어있다면 추가합니다. 하지만, ')' 가 먼저 들어가게 되면 무조건 false 입니다.

2. 스택의 가장 윗 원소와 넣을 원소를 비교합니다. 만약 다르다면 제거합니다.

3. 같다면 계속 추가합니다. 마지막에 스택이 비어있다면 true 입니다.

 

처음 조건에서 '(' 가 먼저 들어갈 수 없으므로, '(' 만 들어갈 수 있습니다. ')'와 '(' 같은 경우는 나올 수 없습니다.

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

bool solution(string s)
{
    bool answer = false;
    
    stack<int> s1;  // 계산할 스택
    
    for(int i=0; i<s.length(); i++)
    {
        if(s1.empty())
        {
            if(s[i] == ')') // 처음 추가가 )라면 무조건 불가
            {
                return answer;
            }
            else
            {
                s1.push(s[i]);  // 비어있다면 추가   
            }
        }
        else
        {
            if(s1.top() == s[i])
            {
                s1.push(s[i]);      // 같다면 제거 불가, 스택에 추가
            }
            else
            {
                s1.pop();           // 다르다면 제거
            }
        }
    }
    
    if(s1.empty())
        answer = true;              // 비어있다면 true

    return answer;
}