프로그래머스 올바른 괄호 C++

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=cpp

알고리즘킷에 들어있던 스택/큐 문제입니다.

 

문자열 s가 주어졌을 때, 이 문자열이 올바른 괄호 문자열인지 확인하는 solution 함수를 구현하는 문제입니다. 올바른 괄호 문자열이란, 모든 '(' 괄호가 반드시 짝을 이루는 ')' 괄호로 닫혀야 함을 의미합니다. 예를 들어, "()()"나 "(())()"는 올바른 괄호 문자열이지만, ")()("나 "(()("는 올바르지 않습니다.

 

즉, 무조건 )을 쓸 때는 앞에 남는 (가 있어야 하고 모든 것이 끝난 후 (가 남아서는 안된다는 말입니다.

 

처음에는 ( 와 )을 담을 스택 두 개를 만들어서 갯수를 비교할까 생각했습니다.이렇게 된다면 어떤 것이 더 많던 모두 올바르지 않은 판정이 가능합니다.

 

하지만 생각해보니까 빼는 것을 한다면 스택은 하나로 충분하다는 생각을 했습니다.

만약 현재 들어온 문자가 '(' 이면 스택에 추가하고, ')'면 스택에서 제거합니다.

 

문자열 형태로 인풋이 들어오고 string의 인덱스 기능 덕분에 따로 파싱하지 않아도 되어서 좋았다.

 

 

 

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

bool solution(string s)
{
    stack<int> _stack;
    
    for(int i = 0; i<s.length(); i++){
        if(s[i] == '('){
        	// ( : 넣기
            _stack.push(0);
        }
        else if(s[i] == ')'){
        	// ( : 제거
            // 하지만 스택이 비어있다면 false 리턴
            if(_stack.empty()){
                return false;
            }
            _stack.pop();
        }
    }
    
    if(_stack.empty()) return true;
    
    // ( 가 남아있다면 false 리턴
    return false;
}