[Programmers/알고리즘 고득점 KIT] 올바른 괄호

[Programmers] 올바른 괄호

Level 2 | #스택/큐 #스택(Stack)

문제 바로가기 🔗

1. 문제 요약

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

문자열 s가 올바른 괄호이면 True를, 아니면 False를 반환한다.

2. 접근 방식 및 포인트

가장 최근에 열린 괄호가 가장 먼저 닫혀야 하므로 LIFO(Last-In-First-Out) 구조인 스택을 활용한다.

• ✅ 열기: '('를 만나면 스택에 무조건 push한다.
• ✅ 닫기: ')'를 만나면 스택에서 pop하여 짝을 맞춘다.
• ✅ 예외: 닫으려는데 스택이 비어있거나, 모든 검사가 끝났는데 스택에 괄호가 남아있으면 잘못된 괄호이다.

3. 구현 코드 (Python)

def solution(s):
    stack = []
    
    for bracket in s:
        # '('는 무조건 push
        if bracket == '(':
            stack.append(bracket)
        # ')'일 때
        else:
            # stack이 비어있으면 짝이 없으므로 즉시 False 반환
            if not stack:
                return False
            stack.pop()
            
    # 마지막에 stack이 완전히 비어야 True (남아있으면 False)
    return not stack

4. ✍️ 회고: 통과만 한다고 정답은 아니다

초기 코드는 프로그래머스 효율성 테스트까지 모두 통과했지만, 스스로 복기하며 치명적인 논리적 결함을 발견했다.

🚫 초기 코드의 논리적 오류

기존 조건: if not stack or bracket == '('

이 조건은 ')'가 가장 먼저 들어올 때도 스택에 추가해버린다. 이후 또 다른 ')'가 들어오면 기존의 ')'를 꺼내며 스택이 비게 된다. 결과적으로 "))" 같은 명백한 오답을 True로 판단하는 오류가 있었다.

💡 배운 점

• 엣지 케이스의 힘: 테스트 케이스가 통과되었다고 안심하지 말고, 직접 반례를 대입해보는 습관의 중요성을 배웠다.
• 명확한 예외 차단: 닫는 괄호가 나왔을 때 짝을 찾을 수 없는 상태라면 즉시 종료하는 설계가 훨씬 견고하다.
• 성능보다 논리: 어떤 입력값에도 흔들리지 않는 로직을 설계하는 연습이 우선되어야 함을 다시 한번 새겼다.