프로그래머스 — 올바른 괄호

---

0. 한눈에 보기

한 줄 요약: '('는 push, ')'는 pop. 중간에 스택이 비었거나 끝까지 스택이 남으면 false.

---

1. 문제

괄호가 바르게 짝지어졌다는 것은 '('로 열렸으면 반드시 ')'로 닫혀야 한다는 뜻이다.

• 올바른 예: "()()", "(())()"
• 올바르지 않은 예: ")()(", "(()("

'(' 또는 ')'로만 이루어진 문자열 s가 주어질 때, 올바른 괄호이면 true, 아니면 false를 반환한다.

제한사항

• 문자열 s의 길이: 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')'로만 구성

입출력 예

---

2. 풀이 아이디어

괄호 짝 맞추기는 스택이 잘 맞는 대표 유형이다.

1. '('를 만나면 스택에 push — “아직 닫히지 않은 열림”을 기록
2. ')'를 만나면
   • 스택이 비어 있으면 → 짝이 될 열림이 없음 → 즉시 false
   • 비어 있지 않으면 → pop으로 짝을 하나 소모
3. 문자열을 다 본 뒤
   • 스택에 남은 '('가 있으면 → 닫히지 않은 열림이 있음 → false
   • 스택이 비어 있으면 → true

길이 제한이 10만이라, 한 번 순회하는 O(n) 풀이면 충분하다.

---

3. 코드

function solution(s) {
    var answer = true;
    let stack = [];

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') stack.push('(');
        else if (s[i] === ')') {
            if (stack.length === 0) return false;
            stack.pop();
        }
    }

    if (stack.length > 0) return false;

    return answer;
}

동작 흐름

예시 추적

"()()" → true

끝에서 스택이 비어 있으므로 true.

")()(" → false

"(()(" → false

끝에서 스택에 2개가 남아 false.

---

4. 정리

• 올바른 괄호 판별은 스택(또는 카운터) 로 풀 수 있다.
• 이번 풀이는 스택에 '('를 쌓고 ')'에서 pop하는 방식이다.
• 중간에 스택이 비었는데 ')'가 오거나, 끝까지 스택이 비지 않으면 올바르지 않다.
• 문자열을 한 번만 보면 되므로 시간 복잡도 O(n), 제한(10만)에도 문제없다.

참고 — 카운터로 줄이기

스택에 실제 문자를 넣을 필요 없이, 열린 괄호 개수만 세어도 같은 판정이 가능하다.

function solution(s) {
    let count = 0;

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') count++;
        else {
            if (count === 0) return false;
            count--;
        }
    }

    return count === 0;
}

의미는 동일하고, 공간은 O(1)로 줄어든다.