균형 잡힌 괄호 표현식(balanced expression)이란 모든 종류의 괄호가 올바른 순서로 쌍을 이루고 있는 식을 의미합니다. 즉, 여는 괄호 하나하나마다 그에 대응하는 닫는 괄호가 정확한 순서로 존재해야 합니다.
표현식 − {([][]{})({}[]{})}
결과 − 균형 잡힘(Balanced)
문제 정의
이 문제에서는 주어진 개수의 괄호로 만들 수 있는 모든 균형 잡힌 표현식을 생성해야 하며, 단 하나의 조건이 붙습니다. 바로 지정된 위치에는 반드시 여는 괄호가 와야 한다는 것입니다.
구체적으로 정수 n과 길이가 2n인 배열(각 위치의 괄호 정보)이 입력으로 주어졌을 때, 값이 1로 표시된 위치에는 반드시 여는 괄호 '{'가 오도록 하면서 길이 2n의 균형 잡힌 표현식이 총 몇 개 만들 수 있는지 구하는 것이 목표입니다.
예제 −
입력 : n = 2, position = [1, 0, 0, 0]
출력 : 2
설명 : 가능한 모든 결과는 {{}} , {}{} 입니다.알고리즘
값이 1인 위치는 모두 여는 괄호로 고정됩니다.
다음 규칙에 따라 재귀적으로 탐색을 진행합니다.
(여는 괄호 개수 − 닫는 괄호 개수)가 음수가 되면, 즉 닫는 괄호가 더 많아지는 순간 유효하지 않은 식이 되므로 0을 반환합니다.
모든 위치를 끝까지 순회한 뒤 열린 괄호의 잔여 개수가 0이면 1(유효한 해답)을 반환하고, 그렇지 않으면 0을 반환합니다.
현재 위치에 1이 미리 할당되어 있다면, 선택의 여지가 없으므로 인덱스를 하나 증가시키고 여는 괄호 수를 늘린 상태로 재귀 호출합니다.
그렇지 않다면 현재 인덱스에 여는 괄호를 넣는 경우와 닫는 괄호를 넣는 경우, 두 가지로 분기하여 각각 재귀 호출한 뒤 그 결과를 더합니다.
프로그램
#include <bits/stdc++.h>
using namespace std;
int find(int index, int openbrk, int n, int expression[]){
if (openbrk < 0)
return 0;
if (index == n){
if (openbrk == 0)
return 1;
else
return 0;
}
if (expression[index] == 1) {
return find(index + 1, openbrk + 1, n, expression);
} else {
return find(index + 1, openbrk + 1, n, expression) + find(index + 1, openbrk - 1, n, expression);
}
}
int main() {
int n = 3;
int expression[6] = { 1, 0, 1, 0, 0, 0};
cout << find(0, 0, 2 * n, expression) << endl;
return 0;
}출력
3
동작 원리 살펴보기
위 프로그램에서 n = 3이고 배열이 {1, 0, 1, 0, 0, 0}이므로, 0번째와 2번째 위치에는 반드시 여는 괄호가 와야 합니다. 이 조건을 만족하는 길이 6의 균형 잡힌 표현식은 다음 세 가지입니다.
{}{}{}
{}{{}}
{{{}}}
따라서 최종 출력은 3이 됩니다. 이 알고리즘은 각 자유 위치마다 여는 괄호와 닫는 괄호를 넣는 두 가지 경우를 모두 시도하는 완전 탐색 방식이며, 중간에 닫는 괄호가 초과되는 가지는 즉시 잘라내기 때문에 불필요한 탐색을 줄일 수 있습니다.