(Python) - 프로그래머스 : 올바른 괄호의 개수

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

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

 

• 해설 :

소괄호의 짝이 n개 주어질 때, 이 소괄호의 짝을 이용해서 만들 수 있는 모든 올바른 괄호열의 개수를 찾는 문제이다.

 

 

 

• 풀이 :

우선 괄호가 올바른 괄호열인지 체크하는 함수를 구현하고, 재귀를 이용해서 n개의 짝으로 만들 수 있는 모든 괄호 문자열에 대해 올바른 괄호열인지 체크하도록 했다. 

 

 

 

 

cnt = 0
 
def check(s):
    stack = []
    for c in s:
        if c == '(':
            stack.append(c)
        else:
            if stack and stack.pop() == '(':
                continue
            else:
                return 0
    if stack:
        return 0
    else:
        return 1
        
        
def dfs(s,l,n,lc,rc):
    global cnt
    if l == n:
        if s[-1] == ")":
            cnt += check(s)
        return
    if lc+1<=n//2:
        dfs(s+"(",l+1,n,lc+1,rc)
    if rc+1<=n//2 and rc < lc:
        dfs(s+")",l+1,n,lc,rc+1)
    
def solution(n):
    global cnt
    dfs("(",1,n*2,1,0)
    return cnt