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

📌 문제

https://programmers.co.kr/learn/courses/30/lessons/12929?language=javascript

📌 풀이

function solution(n) {
  let ans = 0;

  const DFS = (open, close) => {
    if (open + close === n * 2) {
      if (open === n && close === n) ans++;
      return;
    }
    if (open > close) {
      DFS(open, close + 1);
    }
    DFS(open + 1, close);
    return;
  };

  DFS(0, 0);
  return ans;
}

✔ 알고리즘 : DFS

✔ n개의 쌍으로 올바른 괄호열을 만들어야 한다. 올바른 괄호열은 여는 괄호 닫는 괄호가 같고 여는 괄호가 없을 때에 닫는 괄호가 문자열에 들어오면 안된다.

✔ open > close로 여는 괄호가 닫는 괄호보다 많을 때에만 닫는 괄호의 수를 1 증가시킨다.

if (open > close) {
  DFS(open, close + 1);
}

✔ 여는 괄호는 중첩으로 증가할 수 있으므로 DFS탐색을 이어간다

DFS(open + 1, close);

✔ 여닫는 괄호의 합이 2n이고 각각이 n개인 경우에 ans를 1증가 시킨다.

✔ 난이도 : 프로그래머스 기준 LEVEL 4