올바른 괄호의 개수

올바른 괄호의 개수
연습문제 
815명 완료

https://programmers.co.kr/learn/courses/30/lessons/12929

코딩테스트 연습 - 올바른 괄호의 갯수

점화식만 알아낸다면 (그런데 보통 쉽지가 않습니다.)
쉽게 동적계획법으로 풀 수 있습니다. 

카탈란의 수를 아시는 분은 점화식을 떠올려보시길..  
https://suhak.tistory.com/77 https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98

def solution(n):
    array = [1]
    for i in range(n):
        total = 0
        for j in range(i + 1):
            total += array[j] * array[i - j]
        array.append(total)
    return array[n]

 

시뮬레이션으로는 풀 수 없습니다. 

def solution(n):
    from itertools import permutations
    answer = 0
    for each in set(permutations("()" * n)):
        stack = []
        for bracket in each:
            if stack and stack[-1] == '(' and bracket == ')':
                stack.pop()
            else:
                stack.append(bracket)
        if not stack:
            answer += 1
    return answer