[Javascript] 프로그래머스 - 올바른 괄호 갯수

문제 설명

올바른 괄호 문자열이란 ()나 (())처럼 모든 괄호가 올바르게 닫힌 문자열을 의미합니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 올바른 괄호 문자열의 개수를 반환하는 함수를 구현해야 합니다.

---

제한사항

• 1 ≤ n ≤ 14
• n은 정수

---

해결 방법

알고리즘: DFS (백트래킹)

1. left와 right 두 개의 변수를 사용하여 현재까지 사용한 여는 괄호 (와 닫는 괄호 )의 개수를 추적합니다.
2. 여는 괄호가 n보다 작으면 (를 추가하고 재귀 호출합니다.
3. 닫는 괄호가 여는 괄호보다 적다면 )를 추가하고 재귀 호출합니다.
4. left와 right가 모두 n이 되면 유효한 조합이므로 1을 반환합니다.
5. 모든 경우를 탐색한 후, 가능한 경우의 수를 합산하여 반환합니다.

---

시간 복잡도

카탈란 수로, 가능한 괄호 문자열의 개수는 C(n) = (2n)! / (n! (n+1)!) 입니다.
따라서, 시간 복잡도는 O(4ⁿ / √n) 입니다.

---

구현 코드

function solution(n) {
  function dfs(left, right) {
    let count = 0;

    if (left === n && right === n) return 1;
    if (left < n) count += dfs(left + 1, right);
    if (left > right) count += dfs(left, right + 1);

    return count;
  }

  return dfs(0, 0);
}