8.9 괄호

문제 

n-쌍의 괄호로 만들 수 있는 모든 합당한(괄호가 열리고 닫힌) 조합을 출력하는 알고리즘을 구현하여라

 

입력 :3

출력 : ((())), (()()), (())(),()(()),()()()

 

접근법

첫번째는 f(n-1)의 결과로 f(n)을 만드는 재귀적인 방법을 통해 결과쌍을 찾을 수 있을 것이다.

n = 2인경우 (()), ()() 두가지가 있다.

n = 3인경우 (()()) ((())) (()(()) (())() ()()() 5가지가 있다.

그러면  

(())=> (()()) - 첫번째 괄호 다음에 새로운 괄호 넣기 

           ((())) - 두번째 괄호 다음에 새로운 괄호 넣기

          ()(()) - 가장 시작점에 넣는다.

()() => (())() - 첫번째 괄호 다음에 새로운 괄호 넣기

           ()(()) - 두번째 괄호 다음에 새로운 괄호 넣기 

           ()()() - 가장 시작점에 넣는다.

이렇게 보면 중간에 ()(()) 가 중복된다. 이 중복되는 것을 방지하기위해 hash테이블이 필요하기도 하고 중복 처리에 시간이 소요되기 때문이다.

 

문자열 중복 문제를 해결하기 위해서는 처음부터 문자열을 만들어가는 방식을 사용하면 쉽게 해결이 가능하다. 

왼쪽 괄호: 왼쪽 괄호를 다 소진하지 않는 이상 왼쪽 괄호는 항상 삽입한다.

오른쪽 괄호 : 문법 오류가 발생하지 않을떄만 넣을 수 있다. (오른쪽 괄호갯수가 왼쪽괄호갯수보다 큰경우가 오류)

그러면 괄호수만 추적하면 된다!

def addParen(left_r, right_r, char_list,result):
    if left_r < 0  || right_r < left_r :
        return
    elif left_r == 0 || right_r ==0 :
        result.append(''.join(char_list))
    else :
        char_list.append('(')
        addParen(left_r-1, right_r , char_list, result)
        char_list[-1] = ')'
        addParen(left_r, right_r -1, char_list, result)

def Solution(n):
    char_list= []
    result = []
    addParen(n,n,char_list, result)
    return result