title: "[프로그래머스] 올바른 괄호의 갯수 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/12929"
description: "프로그래머스 Level 4 문제 [올바른 괄호의 갯수]의 풀이를 정리합니다."
from collections import Counter
from math import factorial
def find_combinations(n, state, combinations):
if n < 0:
return
if n == 0:
combinations.append(state[:])
return
start = 1 if len(state) == 0 else state[-1]
for nextval in range(start, n+1):
state.append(nextval)
find_combinations(n-nextval, state, combinations)
state.pop()
def mult(arr):
s = 1
for x in arr:
s *= x
return s
def solution(n):
a, b = {}, {}
a[1], b[1] = 0, 1
for i in range(2, n + 1):
# k (2 <= k <= i)개의 수를 합쳐서 i를 만드는 모든 경우의 수를 순회합니다.
# 퇴각검색으로 구현합니다.
state, combinations = [], []
find_combinations(i, state, combinations)
v = 0
for comb in combinations:
if len(comb) == 1:
continue
weight = factorial(len(comb)) / mult(factorial(cnt) for _, cnt in Counter(comb).items())
v += mult(b[x] for x in comb) * weight
a[i] = int(v)
b[i] = a[i-1] + b[i-1]
return a[n] + b[n]
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges