[프로그래머스] Lv2 올바른 괄호 (Python)

문제 링크: 올바른 괄호
알고리즘 분류: # 스택 # 자료구조

---

1. 문제 설명

문자열 s가 주어졌을 때, 괄호가 올바르게 열리고 닫혔는지 여부를 판단하여 True 또는 False를 반환하는 문제입니다.

• () 또는 (())()는 올바른 괄호입니다.
• ) 또는 (()(는 올바르지 않은 괄호입니다.

2. 문제 접근 및 풀이 전략

이 문제는 전형적인 LIFO(Last In, First Out - 후입선출) 구조의 특징을 가지므로 스택(Stack) 자료구조를 사용하면 쉽게 해결할 수 있습니다.

• 열린 괄호 ( 처리: 괄호가 새로 열릴 때는 언제든지 닫힐 가능성이 있으므로 스택에 차곡차곡 쌓아둡니다(append).
• 닫힌 괄호 ) 처리: 닫힌 괄호가 나오면 가장 최근에 열린 괄호와 짝을 맞춰 상쇄시켜야 하므로 스택에서 제거(pop)합니다.
• 예외 처리 (비어있는 스택): 문자열을 순회하는 도중 스택이 비어있는데 닫힌 괄호가 오거나, 처음에 닫힌 괄호부터 시작하는 경우 등을 고려하여 스택의 비어있는 상태(not stack)를 매 순간 체크합니다.
• 최종 판단: 문자열을 모두 돌았을 때 스택이 완전히 비어있다면 모든 괄호가 짝을 찾은 것이므로 True, 남아있다면 False를 반환합니다.

---

3. 정답 코드 (Python)

def solution(s):
    stack = []
    
    for char in s:
        # 스택이 비어있다면 현재 문자를 무조건 삽입
        if not stack:
            stack.append(char)
        else:
            # 열린 괄호는 스택에 추가
            if char == '(':
                stack.append(char)
            # 닫힌 괄호는 직전의 열린 괄호와 짝을 맞추어 제거
            else:
                stack.pop()
                
    # 모든 순회가 끝난 후 스택이 비어있어야 올바른 괄호
    if not stack:
        return True
    else:
        return False

---

4. 효율성 및 복잡도 분석

• 시간 복잡도: $O(N)$
  • 문자열 s를 처음부터 끝까지 딱 한 번만 순회합니다.
  • 파이썬 리스트의 append()와 pop() 연산은 모두 $O(1)$이므로, 전체 시간 복잡도는 문자열 길이 $N$에 비례하는 선형 시간 $O(N)$이 됩니다.

5. 깔끔한 한 줄 요약

"열리면 넣고, 닫히면 뺀다!"
스택의 기본 개념을 정석대로 적용하면 예외 처리까지 한 번에 해결할 수 있는 기분 좋은 문제였습니다.