프로그래머스 문제 풀이 : 올바른 괄호 판단하기

문제 개요

괄호로만 이루어진 문자열 s가 주어졌을 때, 해당 문자열이 올바른 괄호 문자열인지 판단하는 함수를 작성하는 문제입니다.

제한사항

• 문자열 s의 길이는 최대 100,000입니다.
• 문자열은 '(', ')'로만 이루어져 있습니다.

---

문제 해결 전략

이 문제를 해결하기 위한 핵심은 열린 괄호 '(' 와 닫힌 괄호 ')' 의 균형입니다. 이를 위해 다음과 같은 전략을 사용할 수 있습니다.

✅ 조건 정리

1. 열린 괄호가 닫힌 괄호보다 먼저 나와야 합니다.
2. 열린 괄호의 개수와 닫힌 괄호의 개수가 같아야 합니다.

---

해결 방법 1: 카운터 기반 해결

def solution(s):
    count = 0
    for char in s:
        if char == '(':
            count += 1
        else:
            count -= 1
        
        if count < 0:
            return False  # 닫는 괄호가 먼저 나온 경우

    return count == 0  # 열린 괄호와 닫힌 괄호가 같아야 함

🧠 작동 원리

• count를 통해 열린 괄호의 수를 추적합니다.
• count < 0이 되는 순간, 닫힌 괄호가 더 많아지므로 즉시 False 반환.
• 반복이 끝난 후 count == 0이면 괄호가 정확히 짝지어진 상태입니다.

---

해결 방법 2: 스택 자료구조 활용 (선택적 학습용)

def solution(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        else:
            if not stack:
                return False
            stack.pop()
    return not stack

🧠 작동 원리

• 열린 괄호는 스택에 저장하고, 닫힌 괄호가 나올 때 스택에서 제거합니다.
• 닫힌 괄호인데 스택이 비어 있으면 False.
• 반복 후 스택이 비어 있어야 올바른 괄호입니다.

---

시간 복잡도 분석

• 두 방법 모두 **O(N)**의 시간 복잡도를 가집니다.
• 입력 길이가 최대 100,000이라도 효율적으로 동작합니다.

---

결론

이 문제는 자료구조 없이도 해결할 수 있는 대표적인 괄호 문제입니다. 직관적인 로직을 익히는 데 매우 좋은 예제입니다.

✅ 핵심 요약

• 닫힌 괄호가 먼저 나오면 False
• 열린 괄호와 닫힌 괄호의 개수가 일치해야 True
• 카운터 방식이 가장 빠르고 효율적임