[프로그래머스] 올바른 괄호의 개수

문제

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 개수를 반환하는 함수 solution을 완성해 주세요.

제한사항

• 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

입출력 예

입출력 예 설명

예제 #1
2개의 괄호쌍으로 [”(())”, “()()”]의 2가지를 만들 수 있습니다.

예제 #2
3개의 괄호쌍으로 [”((()))”, “(()())”, “(())()”, “()(())”, “()()()”]의 5가지를 만들 수 있습니다.

풀이

매일프로그래밍 3번 문제와 거의 같다.

왼쪽 괄호의 개수는 n과 같을때까지 1씩 추가해준다.
오른쪽 괄호의 개수는 그 이전의 왼쪽 괄호의 개수보다 작거나 같아야 하기 때문에 이 조건을 만족하면 오른쪽 괄호를 하나 추가한다.

오른쪽 괄호의 개수가 n개가 되면 마지막 괄호가 닫힌 것이므로 global variable로 선언한 count를 1 증가시킨다.

using namespace std;

int count = 0;

void parenthesis(int n, int left, int right) {
    if (right == n)
        count++;
    if (left < n)
        parenthesis(n, left + 1, right);
    if (right < left)
        parenthesis(n, left, right + 1);
}

int solution(int n) {
    parenthesis(n, 0, 0);
    return count;
}

출처: https://programmers.co.kr