문제
올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.
제한
- 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수
입출력 예시
| n | result |
|---|---|
| 2 | 2 |
| 3 | 5 |
풀이
결론부터 보고 들어가자. 문제에서 요구하는 정답은 특정 수열의 형태이다. 이를 카탈랑(Catalan) 수라고 부른다. 만약 해당 수열의 형태가 카탈랑 수열에 속하는 것을 알았다면 쉽게 접근이 가능할 것이다. 하지만 나는 이 문제를 풀며 카탈랑 수를 처음 들어봤다. 카탈랑 수열에 대한 설명과 예시 문제는 이 링크에서 보다 자세히 확인할 수 있다. 우리는 일단 이 수열이 카탈랑 수열이라는 점만 미리 캐치하고 하나씩 살펴보며 접근해보자.
1) 규칙 찾기
바로 이전에 포스팅한 문제와 어느정도 접점이 보이는 것 같다. 문제 조건에 의해 괄호쌍의 개수는 최소 1부터 최대 14까지 주어진다. 이때 괄호쌍 1개로 만들 수 있는 경우의 수는 당연히 1이 될 것이다. 또한 예시를 통해 괄호쌍이 2개일 땐 2, 3개일 땐 5의 경우의 수가 존재하는 것을 알 수 있다.
이때 괄호쌍이 2개일 때 나열할 수 있는 경우의 수는 괄호쌍이 1개일 때 나열할 수 있는 경우의 수의 조합으로 나타낼 수 있을 것이다. 또한 3개일 때는 괄호쌍이 2개일 때와 1개일 때, 또는 1개와 2개일 때 등의 조합으로 표현이 가능할 것 같다. 전에 구한 값을 그대로 활용할 수 있다는 점에서 우리는 DP 알고리즘을 떠올릴 수 있다.
문제에서 요구하는 것은 올바른 괄호의 쌍이다. 올바른 괄호란 열린 괄호와 닫힌 괄호의 수가 동일해야 함을 의미한다. 만약 n쌍의 괄호가 있을때 만들 수 있는 경우의 수를 Cn 이라고 표기해보자. 위에서 구한 경우의 수를 다음과 같이 나타낼 수 있을 것이다.
C1=1개C2=2개C3=5개- ...
괄호쌍이 2개(C2)일 때 만들수 있는 조합 중에는 분명히 괄호쌍이 1개(C1)일 때 만들수 있는 조합이 포함될 것이다. 왜냐하면 올바른 괄호쌍만 취급해야 하는데, C1의 개수는 모두 올바른 괄호쌍만 가리키기 때문이다. 따라서 C2는 이미 잘 구성된 C1의 목록에 추가적으로 하나의 괄호쌍을 더 넣는 경우의 수를 고려해주는 것과 같다. 따라서 Cn이라면 다음이 성립한다.
Cn=Cn-1쌍의 괄호 목록에 추가로 하나의 괄호쌍()을 추가한 경우의 수
2) 점화식 추출
앞서 찾은 규칙을 다시 분해해보자. 만약 C3이 주어졌다면 우리는 이를 다음과 같이 분해해서 생각할 수 있다.
C1xC2- 괄호쌍 1개 조합 x 괄호쌍 2개 조합C2xC1- 괄호쌍 2개 조합 x 괄호쌍 1개 조합
앞서 링크된 문제와 달리 순서가 다르면 이는 서로 중복되지 않는다. 직접 예시를 통해 간단하게 확인해보자. C1의 경우 (), C2의 경우 (()) 처럼 나열한다고 가정해보자. 이때 ()(())와 (())()는 서로 다른 올바른 괄호쌍 문자열이다. 때문에 n을 구성하는 모든 조합의 경우의 수의 합으로 Cn을 구할 수 있을 것이다.
그런데 여기서 주의해야 할 점이있다. 접근 방식은 위와 유사하지만 우리는 C1부터 접근해서는 안 된다. 이때는 올바른 괄호쌍의 개수를 제대로 구할 수가 없다. 왜냐하면 3개의 괄호쌍으로 새롭게 생성되는 패턴을 고려해줄 수 없기 때문이다. 역시 위에 링크된 문제와 비교해보면 쉽게 이해할 수 있는데, 이전에 등장한 조합으로는 구성할 수 없는 새로운 패턴이 숫자가 바뀔때마다 등장한다. 하지만 이전 문제와 가장 큰 차이점은 해당 문제에서는 새로운 패턴의 경우의 수가 고정값이 아니라는 점이다.
그렇다면 새로운 패턴이 등장하는 경우의 수를 어떻게 고려해주어야 할까? 약간의 꼼수(?)를 부려보자. Cn이 주어질 때의 경우의 수를 A·B라고 해보자. 이때 A와 B는 그 합이 n이 되는 수라고 하자. 사실 우리는 앞서서 다음의 규칙을 찾았다.
Cn=Cn-1쌍의 괄호 목록에 추가로 하나의 괄호쌍()을 추가한 경우의 수
즉 하나의 괄호쌍 ()을 위 경우에 수에 미리 포함시켜 A·B를 구할 수 없을까? 즉 (A)·B 형태로 조합을 계산할 수 있을 것이다. 이때 각각의 A와 B의 합은 n-1이 되어야 할 것이다. 왜냐하면 이미 하나의 괄호쌍 ()이 추가되었기 때문이다. 이 괄호쌍이 A의 외곽에 추가되었다는 점에 주목하자. 다음과 같은 배치는 중복요소가 발생하기 때문에 적절치 않은 배치이다.
()·A·BA·B·()
위 두가지 배치는 괄호쌍 () 1개를 포함시켰지만 중복여부를 고려하지 않았기 때문에 불가하다. A 또는 B를 포함하도록 괄호쌍을 추가해야 중복요소를 배제한 모든 경우의 수를 제대로 파악할 수 있다. 따라서 다시 C3으로 돌아와 다시 분해하여 계산해보자.
C0xC2: 이미 추가된 괄호1쌍+0쌍+2쌍->(0쌍)·2쌍C1xC1: 이미 추가된 괄호1쌍+1쌍+1쌍->(1쌍)·1쌍C2xC0: 이미 추가된 괄호1쌍+2쌍+0쌍->(2쌍)·1쌍
이때 C0에 조금 주목할 필요가 있다. C0을 우리가 앞서 정의한대로 해석한다면 괄호쌍의 개수가 0개 주어졌을 때 만들 수 있는 모든 가능한 괄호 문자열의 개수를 의미한다. 의미적으로만 따진다면 당연히 0개가 맞다. 애초에 괄호쌍이 주어지지 않았는데 만들 수 있는 경우의 수는 존재하지 않기 때문이다. 그러나 우리는 곱셈을 통해서 모든 경우의 수를 구해주기 때문에 C0의 값을 1로 지정해주어야 한다. 1과 곱셈하는 모든 피연산자는 피연산자의 값을 그대로 반환하기 때문이다. 즉 곱셈의 성질때문에 1로 지정하는 것일뿐, 그 의미가 1개의 문자열을 구성할 수 있다는 것이 아니라는 점에 주의하자!
따라서 우리는 다음과 같은 점화식을 세울 수 있다.
DP[i] = DP[0]*DP[i-1] + DP[1]*DP[i-2] + DP[2]*DP[i-3] + ... + DP[i-1]*DP[0];3) 점화식 적용
점화식을 구했으니 반복문을 통해 정답을 구해주자. 먼저 DP 배열을 선언해주자. 우리는 C0의 값을 사용해주어야 하기 때문에 전달받은 n보다 1이 더 큰 사이즈의 DP 배열을 만들어주어야 한다. 그리고 DP 배열의 첫 번째와 두 번째 값은 모두 1로 초기화해주자.
const dp = new Array(n+1).fill(0);
// dp[0]은 곱셈의 성질에 의해 1로 초기화 한 것이고
// dp[1]은 실제 구성 가능한 올바른 괄호쌍의 개수가 1개이기 때문
dp[0] = dp[1] = 1;
그리고 위에서 구한 점화식을 반복문을 통해 구현해주면 된다.
for(let i = 2; i <= n; i++) {
for(let j = 1; j <= i; j++) {
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];4) 전체코드
이는 사실 초반에 언급한 바와 같이 카탈랑 수열이다. 카탈랑 수열을 이용하는 문제는 괄호쌍 외에도 대각선 피해가기, 산 만들기 또는 다각형을 삼각형으로 나누는 문제에도 다양하게 응용되고 있다. 해당 문제는 N값이 크지 않기 때문에 사실 dfs를 이용한 완전탐색을 이용해서도 풀이가 가능하다. 다만 적절한 가지치기를 통해 최적화가 필요하다. 전체코드 양은 짧지만 만약 카탈랑 수열에 대한 전반적인 지식이 없었다면(내가 그랬다) 생각보다 많은 사고력이 요구되는 문제가 될 것 같다. 주석을 제외한 전체코드는 다음과 같다.
function solution (n) {
const dp = new Array(n+1).fill(0);
dp[0] = dp[1] = 1;
for(let i = 2; i <= n; i++) {
for(let j = 1; j <= i; j++) {
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];
}출처
