[프로그래머스 Lv.2] 올바른 괄호

👌 문제 설명

---

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

---

문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예 설명

---

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

🤔 내가 생각한 아이디어

---

😶‍🌫️ 관찰을 통해 이해해보기& ⚒️ 뚝딱뚝딱 설계

괄호 짝짓기 문제이다. 유명한 parenthesis check문제이고, 보통 '짝짓기'라는 키워드가 나오면 자료구조인 스택을 사용할 수 있다는 아이디어에 착안해서 구현하면 된다.

인풋값으로는 여는 괄호[ '(' ], 닫는 괄호[ ')' ] 2가지의 경우만 나올 수 있다.

여는 괄호가 나왔을 때는 계속 스택에 밀어넣어주고, 닫는 괄호가 나올 때는 스택에서 짝지어줄 수 있는 여는 괄호가 나올 때까지(stk.top=='('까지) 계속 pop()연산을 수행해준다.
다만, 여기서 주의해야 할 점은, 짝지어줄 여는 괄호가 나오기도 전에 스택이 비어버리면 짝지어줄 수 없으므로 false를 리턴해주고 break를 걸어준다.

연산을 다 마치고도 스택이 비어있지 않으면 잉여의 짝지어지지 않은 여는 괄호가 남아있는 것을 뜻하므로 false를 리턴해주는 식으로 작성해주면 된다.

---

💻 정답 코드

---

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

bool solution(string s)
{
    stack<int> stk; //스택 생성
    bool answer = true;
    for(char x : s){
        if(x=='(') {
            stk.push(x);
        } else {
            //스택에서 뽑아준다.
            while(true){
                if(stk.empty()){
                    answer= false; 
                    break;
                }
                if(stk.top()=='(') {
                    stk.pop();
                    break;
                }
                stk.pop();
            }
        }
    }
   if(stk.size()>0){
       answer =false;
   }
    return answer;
}