프로그래머스 12909 - 올바른 괄호

오답 1 (92.3 / 100.0)

#include <string>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

bool solution(string s)
{
    bool answer = true;

    stack<char> stk;
    
    for (char c : s) {
        if (c == '(') {
            stk.push(c);
        } 
        else if (c == ')' && !stk.empty()) {
            stk.pop();
        }
    }
    
    if (stk.empty())
        answer = true;
    else
        answer = false;

    return answer;
}

💥 문제점
(일 때 스택에 ( 추가가 안 돼서 true로 판단됨

---

오답 2 (96.0/100.0)

#include <string>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    int cnt = 0;

    stack<char> stk;
    
    for (char c : s) {
        if (c == '(') {
            stk.push(c);
            cnt++;
        } 
        else if (c == ')' && !stk.empty()) {
            stk.pop();
        }
    }
    
    if (cnt == 0 || !stk.empty())
        answer = false;
    else
        answer = true;

    return answer;
}

🛠️ 개선
(의 개수를 세어서 여는 괄호가 없으면 false 반환

💥 문제점
))) 이렇게 (가 안 나왔을 경우만 고려해서 코드를 개선했는데, ())일 때처럼 계속 짝이 맞다가 마지막에 )가 나오면 for문 내에서 아무런 처리도 하지 않고 있기 때문에 그냥 true가 반환됨

---

정답

#include <string>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    int cnt = 0;

    stack<char> stk;
    
    for (char c : s) {
        if (c == '(') {
            stk.push(c);
        } 
        else if (c == ')' && !stk.empty()) {
            stk.pop();
        }
        else {
            return false;
        }
    }
    
    if (!stk.empty())
        answer = false;
    else
        answer = true;

    return answer;
}

✅ 해결
)인데 pop을 못 하는 상황이면 짝이 맞는 (가 없어서 스택이 비어있는 상황인 것이기 때문에 바로 false를 return