이 문제에서는 정수 n이 주어지며, 우리의 목표는 n개의 균형 잡힌 괄호 쌍으로 만들 수 있는 모든 조합을 출력하는 것입니다.
균형 잡힌 괄호(balanced parentheses)란 모든 여는 괄호에 대응하는 닫는 괄호가 존재하고, 괄호들이 서로 올바르게 중첩된 형태를 의미합니다.
먼저 예시를 통해 문제를 이해해 보겠습니다.
입력: n = 2
출력: {}{} {{}}
문제 해결 접근 방식
이 문제를 해결하려면 괄호 쌍의 개수를 지속적으로 추적해야 합니다. 처음에는 괄호 개수를 0으로 설정한 뒤, 전체 괄호 개수가 n보다 작은 동안 함수를 재귀적으로 호출합니다. 구체적인 로직은 다음과 같습니다.
- 여는 괄호의 개수가 닫는 괄호보다 많으면 닫는 괄호를 추가하고, 남은 쌍에 대해 재귀 호출을 진행합니다.
- 여는 괄호의 개수가 n보다 작으면 여는 괄호를 추가하고, 남은 괄호 쌍에 대해 재귀 호출을 진행합니다.
닫는 괄호의 개수가 n에 도달하면 하나의 완성된 조합이 만들어진 것이므로 해당 문자열을 출력하고 재귀를 종료합니다.
구현 예제
아래 코드는 위에서 설명한 솔루션의 실제 구현을 보여줍니다.
#include <iostream>
using namespace std;
#define MAX_COUNT 100
void printParenthesesPairs(int pos, int n, int open, int close){
static char str[MAX_COUNT];
if(close == n) {
cout<<str<<endl;
return;
}
else {
if(open > close) {
str[pos] = '}';
printParenthesesPairs(pos+1, n, open, close+1);
}
if(open < n) {
str[pos] = '{';
printParenthesesPairs(pos+1, n, open+1, close);
}
}
}
int main() {
int n = 3;
cout<<"All parentheses pairs of length "<<n<<" are:\n";
if(n > 0)
printParenthesesPairs(0, n, 0, 0);
getchar();
return 0;
}
실행 결과
All parentheses pairs of length 3 are −
{}{}{}
{}{{}}
{{}}{}
{{}{}}
{{{}}}
위 실행 결과에서 볼 수 있듯이, n = 3일 때 가능한 모든 균형 잡힌 괄호 조합이 올바르게 출력됩니다. 이 알고리즘은 백트래킹(backtracking) 기법을 활용하여 유효한 조합만을 효율적으로 탐색한다는 점이 특징입니다.