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

• 출처: 프로그래머스 12909
• 분류: 스택/큐 · Lv.2

문제

(와 )로만 이루어진 문자열 s가 올바른 괄호인지 판별하라. "()()", "(())()" → true. ")()(", "(()(" → false.

핵심

(이면 카운터 증가, )이면 감소. 중간에 음수가 되거나 끝났을 때 0이 아니면 false.

풀이

#include <string>

using namespace std;

bool solution(string s) {
    int depth = 0;
    for (char c : s) {
        depth += (c == '(') ? 1 : -1;
        if (depth < 0) return false;
    }
    return depth == 0;
}

메모

• 스택 없이 카운터만으로 충분한 이유: 괄호가 ()한 종류뿐이라 “어떤 괄호가 열려 있는지”를 기억할 필요 없다. 열린 개수만 추적하면 된다.
• depth < 0을 즉시 체크하는 이유: )가 먼저 나오면 짝이 맞을 수 없다. 끝까지 돌 필요 없이 바로 false.
• 괄호가 여러 종류(()[]{})면 스택이 필요하다. top과 현재 닫는 괄호의 종류가 맞는지 확인해야 하기 때문이다.

복잡도

시간	공간
O(N)	O(1)

스택을 쓰면 공간이 O(N)이지만, 카운터 풀이는 O(1).