스텍 / 큐 : 올바른 괄호

문제 이해

주어진 문자열이 올바른 괄호인지 판단하는 문제입니다.

올바른 괄호의 예: "()", "(())()", "(()())"
올바르지 않은 괄호의 예: "((", "))", ")("

---

접근법 1: 개수와 위치 기반 검증

아이디어

올바른 괄호의 조건을 다음과 같이 정의했습니다:

1. '(' 개수와 ')' 개수가 같아야 함
2. 첫 글자는 '('이어야 함
3. 마지막 글자는 ')'이어야 함

구현

import java.util.*;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        
        // 1. 첫 글자와 마지막 글자 확인
        if (s.charAt(0) != '(' || s.charAt(s.length() - 1) != ')') {
            return false;
        }
        
        // 2. 스택을 이용해서 모든 문자 저장
        for (char c : s.toCharArray()) {
            stack.push(c);
        }
        
        // 3. 스택에서 ( 개수와 ) 개수 세기
        int openCount = 0;
        int closeCount = 0;
        
        while (!stack.isEmpty()) {
            char c = stack.pop();
            if (c == '(') {
                openCount++;
            } else {
                closeCount++;
            }
        }
        
        // 4. 개수가 같으면 올바른 괄호
        return openCount == closeCount;
    }
}

결과

• 테스트 케이스 20개 중 18개 통과
• 2개 실패

---

접근법 2: 스택을 이용한 실시간 매칭

아이디어

스택의 본래 목적에 맞게 괄호를 실시간으로 매칭시킵니다:

1. '(' 만나면 스택에 push
2. ')' 만나면 스택에서 pop (매칭할 '('가 없으면 즉시 false)
3. 최종적으로 스택이 비어있으면 모든 괄호가 매칭됨

구현

import java.util.*;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);  // 여는 괄호면 스택에 추가
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    return false;  // 닫는 괄호인데 매칭할 여는 괄호가 없으면 false
                }
                stack.pop();  // 여는 괄호 하나 제거 (매칭 완료)
            }
        }
        
        // 모든 문자를 처리한 후 스택이 비어있어야 올바른 괄호
        return stack.isEmpty();
    }
}

결과

• 모든 테스트 케이스 통과

---

두 접근법 비교

접근법 1의 장점

• 직관적이고 이해하기 쉬운 로직
• 수학적으로 합리적인 조건들

접근법 1의 한계

• 정확히 어떤 케이스에서 실패하는지 불분명
• 아마도 순서 관련 특수한 경우들이 존재하는 것으로 추정

접근법 2의 장점

• 괄호의 순서를 실시간으로 검증
• 스택 자료구조의 LIFO 특성을 적절히 활용
• 모든 테스트 케이스 통과

---

의문점과 해결

처음에는 접근법 1이 실패한 구체적인 반례를 찾기 어려웠습니다. 수학적으로는 다음 조건들을 모두 만족하면 올바른 괄호일 것 같았기 때문입니다:

• '(' 개수 == ')' 개수
• 첫 글자 == '('
• 마지막 글자 == ')'

반례 발견: "())(()"

하지만 다음과 같은 반례를 발견했습니다:

"())(()"

• '(' 개수: 3개, ')' 개수: 3개 ✅
• 첫 글자: '(' ✅
• 마지막 글자: ')' ✅

하지만 이는 올바른 괄호가 아닙니다!

왜 올바르지 않은가?

순서를 따라가보면:

( ) ) ( ( )
1 2 3 4 5 6

- 1번 '('와 2번 ')' 매칭
- 3번 ')'는 매칭할 '('가 없음! ← 여기서 실패
- 4번, 5번 '('와 6번 ')' 매칭되어야 하지만 이미 구조가 깨짐

 

스택 방식으로 확인하면:

'(': 스택 ['(']
')': 스택 [] (매칭 완료)
')': 스택이 비어있는데 ')' 등장 → 즉시 false!

 

왜 순서가 중요한가?

괄호는 실시간으로 매칭되어야 합니다. 즉, ')' 를 만날 때마다 그 앞에 매칭될 '(' 가 있어야 합니다. 단순히 전체 개수만 세는 것으로는 이런 중간 과정의 오류를 잡아낼 수 없습니다.

---

결론

스택을 이용한 실시간 매칭 방식이 안전하고 확실한 해결책입니다. 괄호 문제에서는 단순히 개수만 세는 것보다 순서와 구조를 함께 고려하는 것이 중요합니다.