문제 정의
숫자 n을 입력받으면, n쌍의 괄호를 균형 있게 배치하는 모든 경우의 수를 배열 형태로 반환하는 JavaScript 함수를 작성해야 합니다.
예를 들어 n = 3이라면, 유효한 괄호 조합은 총 5가지이며 출력 결과는 다음과 같습니다.
["()()()", "(())()", "()(())", "(()())", "((()))"]
접근 방법: 재귀와 백트래킹
이 문제는 백트래킹(backtracking) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 여는 괄호는 아직 사용할 개수(left)가 남아 있다면 언제든 추가할 수 있습니다.
- 닫는 괄호는 이미 열린 괄호(right)가 있는 경우에만 추가할 수 있습니다.
- 사용할 괄호가 모두 소진되면(left = 0, right = 0), 완성된 문자열을 결과 배열에 저장합니다.
흥미로운 점은 여는 괄호를 하나 추가할 때마다 right 값을 1 증가시켜, 이후 닫을 수 있는 괄호의 개수를 추적한다는 것입니다. 이렇게 하면 불필요한(균형이 깨진) 조합을 처음부터 생성하지 않으므로 탐색 범위가 크게 줄어듭니다.
구현 예제
다음은 위 로직을 구현한 전체 코드입니다.
const res = [];
const buildcombination = (left, right, str) => {
// 사용할 괄호가 모두 소진되면 결과 저장
if (left === 0 && right === 0) {
res.push(str);
}
// 여는 괄호를 추가할 수 있는 경우
if (left > 0) {
buildcombination(left-1, right+1, str+"(");
}
// 닫을 괄호가 남아 있는 경우
if (right > 0) {
buildcombination(left, right-1, str+")");
}
}
buildcombination(3, 0, "");
console.log(res);
실행 결과
콘솔 출력 결과는 다음과 같습니다.
[ '((()))', '(()())', '(())()', '()(())', '()()()' ]
동작 원리 살펴보기
n = 3으로 함수를 호출하면, 초기 상태는 left = 3, right = 0입니다. 재귀 호출이 진행되면서 각 단계에서 여는 괄호와 닫는 괄호를 선택할지 결정하고, 더 이상 추가할 괄호가 없는 시점에 완성된 문자열을 결과 배열에 push합니다.
이 알고리즘의 시간 복잡도는 카탈란 수(Catalan number)에 비례하며, n쌍의 괄호에 대해 가능한 조합의 수는 C(n) = (2n)! / ((n+1)! × n!) 입니다. 예를 들어 n = 3이면 카탈란 수는 5로, 위 출력 결과의 배열 길이와 일치합니다.