안녕하세요, 여러분! 오늘은 스택의 실제 응용 사례 중 하나인 ‘괄호 검사’에 대해 알아보도록 하겠습니다. 괄호 검사는 프로그래밍에서 매우 중요한 작업 중 하나로, 코드의 구문이 올바른지 확인하는 데 사용됩니다. 처음 들어보시는 분들도 계실 텐데요, 걱정 마세요. 아주 쉽고 재미있게 설명해 드리겠습니다.

먼저, 괄호 검사가 무엇인지 간단히 알아볼까요? 괄호 검사는 주어진 문자열에서 괄호의 짝이 맞는지 확인하는 작업입니다. 예를 들어, ”(()())“는 괄호의 짝이 맞지만, ”(()“는 짝이 맞지 않습니다. 이런 검사를 어떻게 하면 좋을까요? 바로 여기서 스택이 등장합니다!

스택을 이용한 괄호 검사의 기본 아이디어는 이렇습니다

1. 왼쪽 괄호 ’(‘를 만나면 스택에 넣습니다.
2. 오른쪽 괄호 ’)‘를 만나면 스택에서 하나를 꺼냅니다.
3. 마지막에 스택이 비어있으면 괄호의 짝이 맞는 것입니다.

그림 생략.

1. 처음에 스택은 비어있습니다. (스택 1)
2. 첫 번째 ’(‘를 만나면 스택에 push합니다. (스택 2)
3. 두 번째 ’(‘도 스택에 push합니다. (스택 3)
4. ’)‘를 만나면 스택에서 pop합니다. (스택 4)
5. 다시 ’(‘를 만나면 스택에 push합니다. (스택 5)
6. 이후 ’)‘를 만날 때마다 스택에서 pop을 하고, 마지막에는 스택이 비어있게 됩니다. (스택 6)

이 과정을 통해 모든 괄호의 짝이 맞는지 확인할 수 있습니다. 만약 오른쪽 괄호 ’)‘를 만났는데 스택이 비어있거나, 모든 과정이 끝났는데 스택에 괄호가 남아있다면 이는 괄호의 짝이 맞지 않는다는 뜻이 됩니다.

이제 이 과정을 파이썬 코드로 구현해 볼까요?

def is_valid_parentheses(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:  # 스택이 비어있는데 닫는 괄호가 나온 경우
                return False
            stack.pop()

    return len(stack) == 0  # 스택이 비어있으면 True, 아니면 False

# 테스트
print(is_valid_parentheses("((()))"))  # True
print(is_valid_parentheses("(()"))     # False
print(is_valid_parentheses("())"))     # False
print(is_valid_parentheses("((()()))"))  # True

이 코드를 자세히 살펴볼까요?

1. stack = []: 빈 리스트로 스택을 초기화합니다.

2. for char in s:: 문자열의 각 문자를 순회합니다.

3. if char == '(':: 왼쪽 괄호를 만나면 스택에 추가(push)합니다.

4. elif char == ')':: 오른쪽 괄호를 만났을 때,

   • if not stack:: 스택이 비어있다면 짝이 맞지 않으므로 False를 반환합니다.
   • stack.pop(): 스택이 비어있지 않다면 스택에서 하나를 제거(pop)합니다.

5. return len(stack) == 0: 모든 문자를 확인한 후, 스택이 비어있으면 True, 아니면 False를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 왜냐하면 문자열의 각 문자를 한 번씩만 확인하기 때문이죠.

이 괄호 검사 알고리즘은 실제로 많은 곳에서 사용됩니다. 예를 들어

1. 프로그래밍 언어의 컴파일러나 인터프리터: 코드의 구문이 올바른지 확인할 때 사용합니다.
2. 수학 표현식 검증: 수식에서 괄호의 짝이 맞는지 확인할 때 사용합니다.
3. 텍스트 에디터: 괄호 짝 맞추기 기능을 구현할 때 사용합니다.

더 나아가, 이 알고리즘을 확장하면 다양한 종류의 괄호(’()’, ’[]’, ’{}‘)도 함께 검사할 수 있습니다. 이 경우, 스택에 괄호의 종류도 함께 저장하고, 닫는 괄호가 나왔을 때 스택의 top에 있는 괄호와 짝이 맞는지 확인하면 됩니다.

여러분, 이제 스택을 이용한 괄호 검사에 대해 어느 정도 이해가 되셨나요? 처음에는 조금 복잡해 보일 수 있지만, 실제로 구현해보면 생각보다 간단하다는 것을 알 수 있을 거예요.

연습 삼아 다양한 문자열로 이 함수를 테스트해보는 건 어떨까요? 예를 들어, ”((()))(())” 같은 복잡한 괄호 문자열도 정확히 검사할 수 있는지 확인해보세요. 또는 위에서 언급한 대로 여러 종류의 괄호를 처리할 수 있도록 함수를 확장해보는 것도 좋은 연습이 될 거예요.

다음에는 스택과 쌍을 이루는 또 다른 중요한 자료구조인 ‘큐(Queue)‘에 대해 알아보도록 하겠습니다.