올바른 괄호

troubleshooting·3 min read·2026-08-07
cpp#stack#Lv.2
목차

한 줄 요약

(는 push, )는 pop으로 짝을 맞추되, “닫을 게 없는데 닫으려는 경우”와 “끝까지 갔는데 안 닫힌 게 남는 경우” 두 가지를 예외로 처리해야 한다.

왜 (배경/문제 상황)

올바른 괄호 — (와 )로만 이루어진 문자열이 괄호가 올바르게 짝지어졌는지 판단하는 문제.

원인 분석 → 해결 방법

첫 시도부터 정확했다. 다만 두 예외상황이 서로 다른 타이밍에 체크돼야 한다는 점을 명확히 이해하고 넘어갈 필요가 있었다.

bool solution(string s) {
    stack<char> st;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') st.push('(');
        else {
            if (st.empty()) return false; // 예외 1
            st.pop();
        }
    }
    return st.empty(); // 예외 2
}

예외 1 (루프 도중): 닫는 괄호인데 짝지을 여는 괄호가 없음. )를 만날 때마다 스택이 비어있는지 먼저 확인한다. 비어있다는 건 지금까지 열어놓은 괄호가 없다는 뜻이므로, 여기서 닫으려 하면 즉시 false. 예를 들어 ")("는 첫 글자에서 바로 걸린다.

예외 2 (루프 종료 후): 안 닫힌 여는 괄호가 남음. 루프가 끝까지 잘 돌아도, 스택에 뭔가 남아있으면 그건 짝을 못 찾은 (가 있다는 뜻이다. "(()"를 예로 들면 루프는 끝까지 도는데(닫는 괄호 부족으로 중간에 걸리지 않음) 스택에 (가 하나 남아 false가 된다.

두 예외가 서로 다른 시점(루프 중 / 루프 후)에서 체크되는 이유는, 하나는 “당장 이 시점에 모순이 발생”하는 것이고 다른 하나는 “끝까지 가봐야 알 수 있는” 것이기 때문이다.

예제

입력어디서 걸리나
")("루프 중 예외 1 (닫는 괄호가 너무 이름)
"(()"루프 후 예외 2 (여는 괄호가 안 닫힘)
"()()"둘 다 안 걸림 → true

주의사항

  • 스택이 비어있는 상태에서 pop()을 호출하면 정의되지 않은 동작(런타임 에러)이 난다. 항상 empty()를 먼저 확인한다.

참고자료