문제

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미한다.
괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환한다.

아이디어

핵심 아이디어

• 괄호를 하나씩 사용하고 현재 상태에서 올바른 괄호형태가 아니라면 이전 상태로 돌아간다.

구현 아이디어

• 재귀적 방법을 이용하여 구현한다.
  • 현재 상태에서 여는 괄호와 닫는 괄호 사용하는 경우를 모두 체크한다.
  • 여는 괄호/ 닫는 괄호를 모두 n개씩 사용했다면 올바르게 됬다 판단하고 1을 반환한다.
  • 현재 상태에서 닫는 괄호를 여는 괄호보다 많이 사용했다면 올바르지 않다 판단하고 0을 반환한다.
  • 현재 상태에서 여는 괄호/ 닫는 괄호 둘 중 하나가 n개 보다 더 사용됬다면 올바르지 않다 판단하고 0을 반환한다.

코드

def recursive(o: int, c: int, n: int) -> int:
    # o : 사용한 open 괄호 갯수
    # c : 사용한 close 괄호 갯수
    if o == n and c == n:  # 올바르게 괄호 완성한 경우
        return 1
    if o > n or c > n:
        return 0
    if o < c : 
        return 0
    ret = 0
    ret += recursive(o + 1, c, n)
    ret += recursive(o, c + 1, n)
    return ret

def solution(n):
    answer = recursive(0, 0, n)
    return answer