[Python] 프로그래머스 Lv.4 - 올바른 괄호의 갯수

 

 

오늘은 절반 쯤 미해결 문제를 가져왔습니다. 뭔가 문제를 해결할 수 있는 다른 아이디어는 떠오르지만 어떻게 구현할 수 있을지 고민이 깊어져, 풀이에 도움이 될 단서라도 끄적여볼까 싶어서 적어보는 글입니다. 해결한 방법 하나와 고민하고 있는 방법 하나를 같이 소개하며, 오늘은 프로그래머스 난이도 Level.4에 해당하는 '올바른 괄호의 갯수' 문제를 풀어보려고 합니다.

프로그래머스

 

문제

문제 전문은 링크를 통해 직접 확인해주시기 바랍니다.

입력되는 값은 단 하나, 정수 n입니다. 정수 n은 '()' 세트의 갯수입니다. 괄호쌍의 갯수가 주어지면, 이를 통해 만들 수 있는 올바른 괄호('('과 ')'가 순서대로 매칭되는 괄호를 의미함)의 갯수를 구하는 문제입니다. 

 

예시는 다음과 같습니다.

n이 1이 주어진 경우 : result = 1 [ () ]
n이 2가 주어진 경우 : result = 2 [ (()), ()() ]
n이 3이 주어진 경우 : result = 5 [ ((())), (()()), (())(), ()(()), ()()() ]

 

 

첫 번째 아이디어

예시를 다시 가져와보겠습니다.

n = 1 : [ () ]
n = 2 : [ (()), ()() ]
n = 3 : [ ((())), (()()), (())(), ()(()), ()()() ]

 

n = 2인 경우는 n = 1인 경우로 치환이 가능합니다. n = 1인 경우를 [1]이라고 할 때, 다음과 같이 표현이 가능합니다.

n = 2 : [ ([1]), [1][1] ]
i) [1]의 형태를 ( )로 감싼 것
ii) [1]의 형태를 두 개 이어붙인 것 

 

마찬가지로 n = 3인 경우도 n = 1인 경우와 n = 2인 경우로 치환이 가능합니다. n = 2인 경우를 [2]라고 가정합니다.

n = 3 : [ ([2]), ([1][1]), [2][1], [1][2], [1][1][1] ]
i) [2]의 형태를 ( )로 감싼 것
ii) [1]의 형태를 두 개 이어붙여 ( )로 감싼 것
iii) [2]와 [1]을 이어붙인 것
iv) [1]과 [2]를 이어붙인 것
v) [1]의 형태를 세 개 이어붙인 것

 

즉, [n]을 표현하는 방식은 n 미만의 표현을 괄호로 감싸거나 두 가지 이상의 표현을 이어서 표현이 된다는 점입니다.

 

 

두 번째 아이디어

아마 문제에서 요구하는 근본적인 해결책은 이 방법이 아닐까 싶습니다. 바로 '카탈랑 수(Catalan number)' 입니다. 이진 트리 등의 수를 세는 데 사용되는 카탈랑 수는 다음 점화식을 만족하는 수열을 의미합니다. 

$$ C_0 = 1, \quad C_n = \sum_{i=0}^{n} C_i C_{n-i}, \ n \geq 0 $$

 

이 수열의 초항(C1)부터 10번째 항(C10)까지의 값은 다음과 같습니다.

1, 2, 5, 14, 43, 132, 429, 1430, 4862

 

카탈랑 수는 다음과 같은 경우에 사용되는 개념입니다.

 

1. n+2각형을 n개의 삼각형으로 나누는 방법의 갯수

육(6)각형을 4개의 삼각형으로 나누는 경우의 수, n=4이므로 14가지이다.

 

2. n*n의 격자에서 y=x를 넘지않고 (n, n)까지 최단거리로 가는 경우의 수

4x4 격자에서 y=x를 넘지 않고 (4, 4)까지 갈 수 있는 경우의 수는 14가지이다.

 

3. n+1개의 단말 노드를 갖는 이진 순서 트리의 개수

사실 이건 아직도 이해 못 함. 댓글로 설명 해주시면 감사 ~

 

4. 뒤크 단어의 개수

* 뒤크 단어: n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것

XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY

 

 

그리고 마지막으로 이번 문제처럼 올바른 괄호의 갯수를 세는 데도 카탈랑 수가 이용됩니다. 4번 예시의 뒤크 단어를 조금 응용하여 X를 '(', Y를 ')'로 본다면 다음과 같은 예시로 볼 수 있습니다.

((()))     ()(())     ()()()     (())()     (()())

 

즉, 카탈랑 수의 점화식을 구현한다면 이 문제의 답이라고 볼 수 있습니다.

$$ C_0 = 1, \quad C_n = \sum_{i=0}^{n} C_i C_{n-i}={(2n)! \over n!(n+1)!} , \ n \geq 0 $$

 

def factorial(n):
    if n == 1:
        return 1
    return n*factorial(n-1)
    
def solution(n):
    return factorial(2*n)//(factorial(n)*factorial(n+1))

편의상 팩토리얼(n!)을 구하는 부분은 따로 만들어 return을 통해 값을 계산하였습니다.

 

 

마치며

오늘 문제는 '카탈랑 수'라는 개념을 알고 있다면 쉽게 접근할 수 있었겠지만, 저처럼 아무것도 모른 채 막 덤비는 사람은 꽤 머리를 싸맸겠구나 생각하며 다시 한 번 공부의 필요성을 느껴봅니다. 카탈랑 수를 몰랐더라도 첫 번째 아이디어를 구현할 수만 있다면 그것도 하나의 해결 방법이었을텐데 하는 아쉬움이 남지만 아직 코딩 실력이 부족한 저를 탓하며 (ㅠㅠ) 다시 공부에 매진하려고 합니다.