<aside> 💬

lv0, 데이터 구조

괄호 짝 맞추기

문제 설명

주어진 문자열에 포함된 괄호들이 올바르게 짝을 이루고 있는지 확인하는 함수를 작성해주세요. 문자열에는 소괄호 (, ), 중괄호 {, }, 대괄호 [, ]가 포함될 수 있으며, 각각의 괄호는 올바르게 열고 닫혀야 합니다.

예를 들어, 문자열 "{[()()]}"는 올바른 괄호 사용의 예이며, "[(])"는 올바르지 않습니다.

제한 사항

• 문자열의 길이는 최대 1000자입니다.
• 문자열은 (, ), {, }, [, ] 괄호만을 포함할 수 있습니다.

입출력 예

입출력 설명

주어진 문자열에서 괄호들이 올바르게 짝을 이루고 있는지 여부를 반환합니다.

</aside>

😺 풀이 1. 스택과 딕셔너리

def solution(data):
    stack = [] **#1 스택 초기화 및 괄호 매핑**
    bracket_map = {"(": ")", "{": "}", "[": "]"}

    for char in data: **#2 문자열 순회**
        if char in bracket_map: **#3 여는 괄호 확인 및 스택에 추가**
            stack.append(char)
        elif stack and char == bracket_map[stack[-1]]: **#4 닫는 괄호 확인 및 스택 검사**
            stack.pop()
        else: **#5 조건 불충족 시 실패 반환**
            return False

    return not stack **#6 스택 상태 검사 및 결과 반환**

단계별 풀이 전략

1. 스택 초기화 및 괄호 매핑

   열린 괄호를 추적하기 위한 빈 스택(stack)을 생성하고, 괄호의 짝을 쉽게 확인하기 위해, 여는 괄호를 키 값으로, 닫는 괄호를 밸류 값으로 가지는, 딕셔너리(bracket_map)를 생성합니다.

2. 문자열 순회

   주어진 문자열 data의 각 문자 char에 대해 순회를 시작합니다. 이때, 문자열의 각 문자를 하나씩 확인하면서 괄호의 상태를 검사합니다. 딕셔너리를 for문으로 순회할 때는, 기본적으로 키(key)만 반환됩니다. 즉, 여는 괄호만 반환하게 됩니다.

3. 여는 괄호 확인 및 스택에 추가

   만약, 현재 문자가 여는 괄호('(', '[', '{') 중 하나라면, 스택(stack)에 추가합니다. 이는 해당 괄호가 아직 닫히지 않았음을 나타냅니다.

4. 닫는 괄호 확인 및 스택 검사

   현재 문자가 닫는 괄호인 경우, 스택이 비어있지 않고, 스택의 마지막 요소가 현재 닫는 괄호에 대응하는 여는 괄호인지 검사합니다. 이 조건이 참이면, 스택에서 해당 여는 괄호를 제거합니다.

5. 조건 불충족 시 실패 반환

   닫는 괄호가 나타났으나 스택이 비어있거나, 스택의 마지막 요소가 현재 닫는 괄호와 짝이 맞지 않는 경우, 괄호의 짝이 올바르지 않음을 의미하므로 False를 반환합니다.

6. 스택 상태 검사 및 결과 반환

   모든 문자를 검사한 후, 스택이 비어있다면 모든 괄호가 올바르게 짝지어진 것으로 판단하고 True를 반환합니다. 스택에 여는 괄호가 남아있다면, 짝이 맞지 않는 괄호가 있음을 의미하므로 False를 반환합니다.

알아둬야 할 개념

스택(Stack)

• 기본 형태: stack = []

• 개념: 스택은 가장 마지막에 추가된 요소가 가장 먼저 제거되는 구조를 가진 데이터 구조입니다.

  stack = []
  stack.append(1) # stack에 1 추가
  stack.append(2) # stack에 2 추가
  stack.append(3) # stack에 3 추가
  print(stack) # 출력: [1 ,2 ,3]
  
  stack.pop() # stack에 마지막으로 들어간 요소 삭제
  print(stack) # 출력: [1 ,2]
  

딕셔너리

• 기본 형태: dict = {key: value}

• 개념: 딕셔너리는 키(key)와 값(value) 쌍으로 이루어진 자료구조입니다. 각 키는 딕셔너리 내에서 유일해야 하며, 이를 통해 해당 키에 대응하는 값을 빠르게 찾을 수 있습니다. 파이썬의 딕셔너리는 중괄호 {}를 사용하여 정의되며, 각 요소는 키: 값의 형태로 구성됩니다.

  # 딕셔너리 생성
  dict = {'a': 1, 'b': 2}
  
  # 딕셔너리에서 값 읽기
  print(dict['a'])  # 출력: 1 
  
  # 딕셔너리에 새로운 키-값 쌍 추가
  dict['c'] = 3
  
  # 딕셔너리 출력
  print(dict)  # 출력: {'a': 1, 'b': 2, 'c': 3} 
  

풀이 2. 스택