Python에서 유효한 괄호를 확인하는 방법

by

파이썬에서 유효한 괄호 검사하는 방법

이 튜토리얼에서는 파이썬을 사용하여 괄호의 유효성을 확인하는 방법을 상세히 설명합니다. 괄호 문자열이 주어졌을 때, 그 조합이 유효한지 판단하는 것은 코딩 인터뷰에서 자주 등장하는 문제입니다. 이 글을 통해 여러분은 주어진 문자열의 유효성을 검증하는 파이썬 함수를 작성하는 방법을 배우고, 문제를 해결하는 능력을 향상시킬 수 있을 것입니다.

유효한 괄호 문제란 무엇인가?

유효한 괄호 문제란 무엇인지부터 논의를 시작해 보겠습니다. 이 문제는 단순한 괄호 `()`, 중괄호 `{}`, 대괄호 `[]`로 구성된 문자열이 주어졌을 때, 이 괄호 조합이 유효한지 확인하는 것을 목표로 합니다.

유효한 괄호 문자열은 다음과 같은 두 가지 조건을 만족해야 합니다:

  • 모든 열린 괄호는 동일한 유형의 닫힌 괄호와 짝을 이루어야 합니다.
  • 괄호는 올바른 순서대로 닫혀야 합니다.

다음은 유효하거나 유효하지 않은 괄호 문자열의 몇 가지 예입니다:

test_str = "{}]"  --> 유효하지 않음, ]가 열린 적이 없음
test_str = "[{}]" --> 유효함
test_str = "[]"   --> 유효함
test_str = "[]{}" --> 유효함
test_str = "[{]}" --> 유효하지 않음, 괄호가 올바르지 않게 닫힘!

이 문제를 해결하는 데 있어서 스택은 핵심적인 역할을 하는 자료 구조입니다. 다음 섹션에서 스택의 기본 개념을 다시 살펴보겠습니다.

스택 자료 구조 다시 보기

스택은 후입선출(LIFO, Last In First Out) 원칙을 따르는 자료 구조입니다. 스택의 맨 위에 요소를 추가하고, 맨 위에서 요소를 제거하는 방식으로 작동합니다.

스택 맨 위에 요소를 추가하는 것을 ‘푸시’ 연산이라고 하며, 스택 맨 위에서 요소를 제거하는 것을 ‘팝’ 연산이라고 합니다.

이제 다음 두 가지 규칙을 사용하여 괄호 문자열에 적용할 수 있는 일련의 연산을 생각해 보겠습니다.

  • 모든 열린 괄호를 스택에 푸시합니다.
  • 닫힌 괄호를 발견하면 스택 맨 위에서 요소를 팝합니다.

이제 이 지식을 바탕으로 유효한 괄호 검사 문제를 해결해 봅시다.

유효한 괄호 확인 방법

위의 예시들을 종합하여 다음과 같은 접근 방식을 취할 수 있습니다.

괄호 문자열 길이 확인: 길이가 홀수이면 유효하지 않음

모든 열린 괄호는 닫힌 괄호와 짝을 이루어야 하므로, 유효한 문자열은 항상 짝수 개의 문자를 포함해야 합니다. 만약 문자열의 길이가 홀수라면, 괄호 조합이 유효하지 않다는 것을 바로 알 수 있습니다.

# len(test_str) = 3 (홀수); ]는 열린 [가 없음
test_str = "{}]"
# len(test_str) = 3 (홀수); (는 닫는 )가 없음
test_str = "[(]"
# len(test_str) = 5 (홀수); 불필요한 )가 있음
test_str = "{())}"

이제 문자열의 길이가 짝수일 경우 어떻게 처리해야 하는지 알아보겠습니다.

괄호 문자열 길이 짝수: 그 다음은?

1단계: 문자열을 왼쪽에서 오른쪽으로 순회합니다. 문자열을 `test_str`이라 하고, 문자열 내의 각 문자를 `char`이라고 부르겠습니다.

2단계: 첫 번째 문자 `char`가 열린 괄호(`(`, `{`, `[`)이면 스택 맨 위에 푸시하고, 문자열의 다음 문자로 진행합니다.

3단계: 다음 문자(`char`)가 열린 괄호인지 닫힌 괄호인지 확인합니다.

3.1단계: 만약 열린 괄호라면, 스택에 다시 푸시합니다.

3.2단계: 만약 닫힌 괄호라면, 스택 맨 위에서 팝하고 4단계로 넘어갑니다.

4단계: 여기에서 스택에서 팝한 값에 따라 세 가지 가능성이 있습니다.

4.1단계: 만약 팝한 값이 같은 종류의 열린 괄호라면, 3단계로 돌아갑니다.

4.2단계: 만약 팝한 값이 다른 종류의 열린 괄호라면, 해당 괄호 문자열은 유효하지 않다고 결론지을 수 있습니다.

4.3단계: 마지막 가능성은 스택이 비어있는 경우입니다. 이는 매칭되는 열린 괄호 없이 닫힌 괄호가 나타난 경우이므로, 문자열이 유효하지 않다는 것을 의미합니다.

유효한 괄호 문자열 예시

이제 위에서 설명한 단계를 세 가지 예시를 통해 자세히 살펴보겠습니다.

📑 이미 작동 방식을 이해했다면, 다음 섹션으로 건너뛰어도 좋습니다.

#1. 첫 번째 예시로, `test_str = “{()”`라고 가정해 봅시다.

  • `{`는 첫 번째 문자이며, 열린 괄호이므로 스택에 푸시합니다.
  • 다음 문자 `(` 또한 열린 괄호이므로, 스택에 푸시합니다.
  • 세 번째 문자 `)`는 닫힌 괄호이므로, 스택 맨 위에서 요소를 팝합니다. 팝한 값은 `(`입니다.
  • 이 시점에서 문자열의 끝에 도달했지만, 스택에는 여전히 열린 `{`가 남아 있으며, 이는 닫히지 않은 상태입니다. 따라서 주어진 괄호 문자열 `test_str`은 유효하지 않습니다.

#2. 두 번째 예시로, `test_str = “()]”`라고 가정해 봅시다.

  • 첫 번째 문자 `(`는 열린 괄호이므로 스택에 푸시합니다.
  • 두 번째 문자 `)`는 닫힌 괄호입니다. 스택 맨 위에서 팝합니다. 스택에서 팝한 값은 `(`로, 동일한 유형의 열린 괄호입니다. 다음 문자로 넘어갑니다.
  • 세 번째 문자 `]`는 닫힌 괄호이며, 스택 맨 위에서 다시 팝해야 합니다. 그러나 스택이 비어 있다는 것을 알 수 있습니다. 이는 매칭되는 열린 괄호 `[`가 없다는 의미입니다. 따라서 이 문자열은 유효하지 않습니다.

#3. 마지막 예시로, `test_str = “{()}”`이라고 가정해 봅시다.

  • 처음 두 문자 `{(`는 열린 괄호이므로 스택에 푸시합니다.
  • 세 번째 문자는 닫힌 `)`이므로, 스택 맨 위에서 팝합니다. 팝한 값은 `(`입니다.
  • 다음 문자 `}`는 닫힌 중괄호이고, 스택 맨 위에서 팝하면 `{` 열린 중괄호를 얻게 됩니다.
  • 전체 문자열을 순회한 후 스택이 비어있으므로 `test_str`은 유효합니다! ✅

📌 유효한 괄호 검사 문제의 단계를 요약한 다음 순서도를 참조용으로 저장해 두세요!

다음 섹션에서는 이 개념을 파이썬 코드로 어떻게 옮길 수 있는지 살펴보겠습니다.

파이썬으로 유효한 괄호 검사 프로그램 구현하기

파이썬에서는 리스트를 사용하여 스택을 흉내낼 수 있습니다.

`append()` 메서드를 사용하여 리스트의 끝에 요소를 추가할 수 있습니다. 이것은 스택의 맨 위에 푸시하는 것과 유사합니다.

`pop()` 메서드는 리스트에서 마지막 요소를 반환하며, 이는 스택 맨 위에서 팝하는 것과 유사합니다. 즉, 가장 최근에 추가된 요소를 제거합니다.

이제 파이썬 리스트에서 푸시 및 팝 연산을 구현하여 스택을 모방하는 방법을 알게 되었습니다.

다음 단계로, 열린 괄호와 닫힌 괄호를 어떻게 구별할 수 있을까요?

파이썬 딕셔너리를 사용하여 열린 괄호 `'{‘`, `'[‘`, `'(‘`를 딕셔너리의 키로 하고, 해당하는 닫힌 괄호 `’}’`, `’]’`, `’)’`를 값으로 사용할 수 있습니다. `.keys()` 메서드를 사용하여 딕셔너리의 개별 키에 접근할 수 있습니다.

이제 배운 모든 것을 활용하여 `is_valid()` 함수를 정의해 보겠습니다.

함수 정의 이해하기

함수 정의가 포함된 다음 코드를 확인해 보세요. 위의 설명과 순서도 단계를 사용한 것을 알 수 있을 것입니다.

또한, 독스트링을 포함했습니다:

  • 함수에 대한 간략한 설명
  • 함수 호출에 사용되는 인수
  • 함수가 반환하는 값

▶ `help(is_valid)` 또는 `is_valid.__doc__`를 사용하여 독스트링을 확인할 수 있습니다.

def isValid(test_str):
  '''주어진 괄호 문자열이 유효한지 검사합니다.
  
  Args:
      test_str (str): 검사할 괄호 문자열
    
  Returns:
      True if test_str이 유효하면 True, 그렇지 않으면 False
  '''
  # len(test_str)이 홀수면 -> 유효하지 않음!
  if len(test_str)%2 != 0:
    return False
  # 괄호 딕셔너리 초기화
  par_dict = {'(':')','{':'}','[':']'}
  stack = []
  for char in test_str:
    # 열린 괄호를 스택에 푸시
    if char in par_dict.keys():
      stack.append(char)
    else:
      # 매칭되는 열린 괄호 없이 닫힌 괄호가 나타난 경우
      if stack == []:
          return False
      # 닫힌 괄호 -> 스택 맨 위에서 팝
      open_brac = stack.pop()
      # 매칭되지 않는 괄호 -> 유효하지 않음!
      if char != par_dict[open_brac]:
        return False
  return stack == []

파이썬 함수 `is_valid`는 괄호 문자열이 유효한지 확인하며, 다음과 같이 작동합니다.

  • `is_valid` 함수는 검사할 괄호 문자열인 `test_str`을 매개변수로 받습니다. 함수는 `test_str` 문자열이 유효한지 여부에 따라 `True` 또는 `False`를 반환합니다.
  • 여기서 `stack`은 스택을 흉내내는 파이썬 리스트입니다.
  • 그리고 `par_dict`는 열린 괄호를 키로, 닫힌 괄호를 해당 값으로 사용하는 파이썬 딕셔너리입니다.
  • 문자열을 탐색하는 동안 괄호 문자열을 유효하지 않게 만드는 조건이 발생하면 함수는 `False`를 반환하고 종료합니다.
  • 문자열의 모든 문자를 순회한 후, `stack == []`를 통해 스택이 비어 있는지 확인합니다. 만약 비어 있다면 `test_str`은 유효하며 함수는 `True`를 반환합니다. 그렇지 않으면 함수는 `False`를 반환합니다.

이제 함수가 제대로 작동하는지 확인하기 위해 몇 가지 함수 호출을 시도해 보겠습니다.

str1 = '{}[]'
isValid(str1)
# 출력: True

str2 = '{((}'
isValid(str2)
# 출력: False

str3 = '[{()}]'
isValid(str3)
# 출력: True

str4 = '[{)}]'
isValid(str4)
# 출력: False

str5 = '[[]}'
isValid(str5)
# 출력: False

위의 코드에서 함수가 예상대로 작동한다는 것을 확인할 수 있습니다!

결론 🧑‍💻

배운 내용을 간단히 요약해 보겠습니다.

  • 먼저 유효한 괄호 검사 문제에 대해 알아보았습니다.
  • 다음으로, 스택을 데이터 구조로 사용하여 문제를 해결하는 방법을 배웠습니다.
  • 그 다음, 열린 괄호를 키로, 해당 닫힌 괄호를 값으로 사용하는 파이썬 딕셔너리를 활용하여 괄호 조합을 검증하는 방법을 배웠습니다.
  • 마지막으로, 주어진 괄호 문자열이 유효한지 확인하는 파이썬 함수를 정의했습니다.

다음 단계로, koreantech.org의 온라인 파이썬 편집기에서 직접 코드를 작성해 보세요. 도움이 필요하면 언제든지 이 가이드를 다시 참조하세요!

더 많은 파이썬 튜토리얼을 확인해 보세요. 즐거운 코딩 되세요! 🎉