[프로그래머스 고득점 Kit] 올바른 괄호 C++ 문제 풀이

#INFO

분류 : 스택/큐

난이도 : LEVEL2

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

프로그래머스

---

#SOLVE

간단한 스택 문제 입니다.

주어진 문자열 s가 올바른 괄호 인지를 판별해야 합니다. (올바른 괄호란 여는 괄호 '(' 로 시작해 닫는 괄호 ')' 로 끝나는 문자열입니다. 에를들어 )( 는 올바른 괄호가 될 수 없습니다.)

 

문제 풀이 아이디어는 간단합니다.

우선, 문자열 s의 각 괄호를 저장할 char형 스택을 하나 선언합니다.

stack<char> stk;

 

다음으로 문자열 s를 순회하며 왼쪽 괄호 '(' 인 경우에는 스택에 푸시합니다. 

 

오른쪽 괄호 ')' 인 경우에는 두 가지 케이스로 나뉩니다.

첫 번째 케이스는 오른쪽 괄호 ')'이고, 스택이 비어있지 않은 케이스 입니다. 

이 때 왼쪽 괄호를 스택에서 pop 합니다.

 

두 번째 케이스는 오른쪽 괄호 ')' 이고, 스택이 비어있는 케이스 입니다. 

스택에 오른쪽 괄호 ')'를 그냥 푸시합니다. 

 

이제 오른쪽 괄호가 스택에 하나라도 push가 된 이상, 왼쪽 괄호 '(' 혹은 오른쪽 괄호 ')' 가 아무리 들어와도 스택이 비는 경우가 발생하지 않습니다. 즉, 스택이 비어있지 않으면 올바르지 않은 괄호가 됩니다. 

 

위 과정을 코드로 나타내면 다음과 같습니다.

    for(const auto& i : s){
        if(i == '(') stk.push('(');
        else if(i == ')'){
            if(!stk.empty()){ 
                stk.pop();
            }
            else{ 
                stk.push(')');
            }
        }
    }
    if(!stk.empty()) answer = false;

---

#CODE

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

bool solution(string s)
{
    bool answer = true;
    stack<char> stk;
    for(const auto& i : s){
        if(i == '(') stk.push('(');
        else if(i == ')'){
            if(!stk.empty()){ 
                stk.pop();
            }
            else{ 
                stk.push(')');
            }
        }
    }
    if(!stk.empty()) answer = false;
    return answer;
}