올바른 괄호의 갯수

문제 설명

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

 

제한사항

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

---

입출력 예

 

입출력 예 설명

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

 

import java.util.*;

class Solution {
	static int answer = 0;

	public int solution(int n) {
		int left = n;
		int right = n;
		dfs(left, right);
		return answer;
	}

	static void dfs(int left, int right) {
		if (left == 0 && right == 0) {	// 괄호를 모두 사용하면 경우의 수 1 늘리고 종료
			answer++;
			return;
		}

		if (right > left || left < 0 || right < 0)	// 괄호의 갯수 제한이 넘거나 닫힌 괄호가 열린 괄호보다 많으면 종료
			return;

		dfs(left - 1, right);
		dfs(left, right - 1);
	}
}

 

문제출처

https://programmers.co.kr/learn/courses/10302/lessons/62952