Python으로 다양한 종류의 괄호가 균형 잡혀 있는지 확인하는 방법

소괄호 (), 중괄호 {}, 대괄호 []로 이루어진 문자열이 주어졌을 때, 이 괄호들이 균형 잡힌(well-formed) 올바른 형태인지 확인하는 문제입니다.

예를 들어 입력이 s = "([()()]{[]})()"라면 모든 괄호가 올바르게 짝을 이루고 있으므로 결과는 True가 됩니다.

문제 해결 접근 방식

이 문제는 스택(Stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.

• 빈 리스트로 스택(stack)을 초기화합니다.
• 닫는 괄호를 키로, 여는 괄호를 값으로 갖는 해시 맵을 생성합니다. 즉, {'}': '{', ')': '(', ']': '['} 형태입니다.
• 문자열 s의 각 문자 c를 순서대로 검사합니다.
  • c가 닫는 괄호('}', ')', ']') 중 하나라면:
    • 스택이 비어 있거나, 스택의 최상단(top) 요소가 d[c](짝이 되는 여는 괄호)와 일치하지 않으면 False를 반환합니다.
    • 그렇지 않다면 스택에서 해당 요소를 제거(pop)합니다.
  • c가 여는 괄호라면 스택에 추가(push)합니다.
• 모든 문자를 처리한 후 스택이 비어 있으면 True, 그렇지 않으면 False를 반환합니다.

스택이 비어 있다는 것은 모든 여는 괄호가 정확히 짝지어진 닫는 괄호와 만났다는 의미이므로, 문자열이 균형 잡혀 있다고 판단할 수 있습니다.

Python 구현 예제

class Solution:
    def solve(self, s):
        stack = []
        d = {'}': '{', ')': '(', ']': '['}
        for c in s:
            if c in '}])':
                if not stack or stack[-1] != d[c]:
                    return False
                stack.pop()
            else:
                stack.append(c)
        return not stack

ob = Solution()
print(ob.solve("([()()]{[]})()"))

입력

"([()()]{[]})()"

출력

True

시간 복잡도 분석

이 알고리즘은 문자열의 각 문자를 한 번씩만 순회하므로 시간 복잡도는 O(n)이며, 최악의 경우 모든 문자가 여는 괄호일 때 스택에 저장되므로 공간 복잡도 역시 O(n)입니다. 컴파일러나 코드 편집기의 구문 검사, 수식 유효성 검증 등 실제 개발 환경에서도 널리 활용되는 기본적인 알고리즘입니다.