프로그래머스

프로그래머스 올바른 괄호 풀이: 카운터로 여는 괄호 관리

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 올바른 괄호
  • 출처: 프로그래머스 코딩테스트 연습, 스택/큐
  • 자체 판단 난이도: Level 2

괄호를 왼쪽부터 순서대로 확인하면서 열려 있는 괄호의 개수만 관리하면 되는 문제다. 닫는 괄호가 먼저 나오는 경우와 모든 문자를 처리한 뒤 여는 괄호가 남는 경우를 구분하면 되므로 Level 2로 판단했다.

1. 문제 요약

문자열 s가 (와 )로만 이루어져 있을 때, 괄호가 올바르게 짝지어졌는지 판정한다.

  • (는 아직 닫히지 않은 괄호 하나를 추가한다.
  • )는 이전에 열려 있는 괄호 하나를 닫아야 한다.
  • 어떤 시점에도 닫는 괄호 수가 앞선 여는 괄호 수보다 많으면 안 된다.
  • 문자열 끝에서 여는 괄호가 남아 있으면 안 된다.

예를 들어 "()()"와 "(())()"는 올바른 괄호이고, ")()("와 "(()("는 올바르지 않다. 문자열 길이는 최대 100,000이다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

상태 전이와 경계 처리

balance를 현재까지 읽은 부분에서 닫히지 않은 여는 괄호의 개수로 정의한다.

  • (를 읽으면 balance += 1
  • )를 읽으면 balance -= 1

각 문자를 처리한 직후 balance < 0이면 현재 닫는 괄호에 대응할 여는 괄호가 없다는 뜻이다. 이후 문자를 확인해도 올바른 괄호가 될 수 없으므로 즉시 False를 반환한다.

문자열 전체를 처리한 뒤 balance == 0이어야 모든 여는 괄호가 닫힌 것이다. 양수로 남아 있으면 여는 괄호가 부족하게 닫힌 상태이므로 False다.

닫는 괄호가 카운터만으로 충분한 이유

괄호 종류가 (와 ) 하나씩뿐이므로 스택에 실제 괄호 문자를 저장하지 않고 개수만 저장해도 된다. 닫는 괄호는 항상 가장 최근의 열린 괄호와 짝을 이루지만, 모든 열린 괄호가 동일한 종류이기 때문에 어떤 문자를 pop했는지 기록할 필요가 없다.

따라서 스택의 크기와 같은 balance 하나만으로 현재 상태를 표현할 수 있다.

불변식

문자열의 앞에서부터 일부를 처리한 뒤 balance는 다음 의미를 가진다.

balance = 지금까지 읽은 '('의 개수 - 지금까지 읽은 ')'의 개수

올바른 괄호가 될 가능성이 남아 있으려면 모든 접두사에서 balance >= 0이어야 한다. 마지막에는 전체 여는 괄호와 닫는 괄호가 같은 수여야 하므로 balance == 0이어야 한다.

오답 접근과 반례

문자열 전체에서 (와 )의 개수만 비교하면 부족하다.

s = ")("

두 종류의 개수는 각각 1개로 같지만, 첫 문자에서 닫는 괄호가 먼저 나와 대응할 여는 괄호가 없다. 따라서 처리 중간에 balance가 음수가 되는지 확인해야 한다.

반대로 중간에 음수가 되는 순간을 확인하지 않고 마지막 balance == 0만 검사하면 이 반례를 올바른 괄호로 잘못 판단한다. 스택에 모든 괄호를 저장하는 방식은 가능하지만, 이 문제에서는 카운터 하나만으로 같은 상태를 표현할 수 있다.

시간·공간 복잡도

문자열을 왼쪽부터 한 번 순회하므로 시간 복잡도는 O(n)이다. 괄호 개수 하나만 저장하므로 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

def solution(s):
    balance = 0

    for bracket in s:
        if bracket == "(":
            balance += 1
        else:
            balance -= 1

        if balance < 0:
            return False

    return balance == 0

문제의 입력은 ( 또는 )만 포함하므로 else는 닫는 괄호를 의미한다. 닫는 괄호를 처리한 직후 balance를 확인하면 잘못된 접두사를 발견하는 즉시 종료할 수 있다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 접두사 유효성과 마지막 잔량 조건을 확인할 수 있다.

assert solution("()()") is True
assert solution("(())()") is True
assert solution(")()(") is False

4. 공식 예제와 추가 검증

공식 예제와 한 종류의 괄호만 있는 경우, 중간에 닫는 괄호가 먼저 나오는 경우를 Python 코드로 실행했다.

공식 예제

입력 기대 출력 확인 결과
"()()" True 통과
"(())()" True 통과
")()(" False 통과
"(()(" False 통과

추가 검증 1: 여는 괄호 하나

입력: s = "("
기대 출력: False
확인 결과: 통과
검증 목적: 문자열 끝에 닫히지 않은 여는 괄호가 남는지 확인

추가 검증 2: 닫는 괄호 하나

입력: s = ")"
기대 출력: False
확인 결과: 통과
검증 목적: 첫 문자부터 balance가 음수가 되는 경우의 조기 종료 확인

추가 검증 3: 깊게 중첩된 괄호

입력: s = "(((())))"
기대 출력: True
확인 결과: 통과
검증 목적: balance가 증가했다가 0으로 정확히 돌아오는지 확인

추가 검증 4: 여러 묶음과 중첩 조합

입력: s = "()((()))()"
기대 출력: True
확인 결과: 통과
검증 목적: 독립된 괄호 묶음과 중첩 묶음을 연속으로 처리하는지 확인

5. 다른 풀이 방식 검색 및 비교

실제 스택에 (를 넣고 )에서 pop하는 방식은 괄호 구조를 직관적으로 보여준다. 하지만 이 문제는 괄호 종류가 하나뿐이므로 스택의 내용이 항상 같은 문자다. 따라서 스택의 크기만 카운터로 유지하면 동일한 O(n) 시간에 O(1) 공간으로 최적화할 수 있다.

마무리

올바른 괄호는 현재까지 닫히지 않은 여는 괄호의 수를 관리하는 문제다. 모든 접두사에서 카운터가 음수가 되지 않아야 하고, 마지막에 0이어야 한다는 두 조건을 확인하면 실제 스택 없이도 괄호의 유효성을 O(n) 시간과 O(1) 공간으로 판정할 수 있다.

#스택#프로그래머스#난이도 2