[매일코딩#002] | 재귀함수와 문자열을 응용한 알고리즘

STUDY/매일코딩

[매일코딩#002] | 재귀함수와 문자열을 응용한 알고리즘

돤주 2019. 9. 17. 00:10

정수 n이 주어지면, n개의 여는 괄호 "("와 n개의 닫는 괄호 ")"로 만들 수 있는 괄호 조합을 모두 구하시오. (시간 복잡도 제한 없습니다).

Given an integer N, find the number of possible balanced parentheses with N opening and closing brackets.

예제)
Input: 1
Output: ["()"]

Input: 2
Output: ["(())", "()()"]

Input: 3
Output: ["((()))", "(()())", "()(())", "(())()", "()()()"]

 
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input("정수를 입력해주세요: "))
 
def foo(n):
    if n == 1:
        return ['()']
    else:
        result = []
        temp = foo(n-1)
        for i in range(len(temp)):
            result.append('('+temp[i]+')')
            result.append('()'+temp[i])
            result.append(temp[i]+'()')
        result.remove('()'*n)
        return result
 
print(foo(n))
cs
 

알고리즘 문제들은 재귀함수를 진짜 좋아하는 것 같다 .. ㅎ ㅏ ..

재귀함수랑 친해져야지 ㅠㅅㅠ

그래도 이번 문제는 나름 수월하게 풀렸다 ㅎㅎ 뿌듯