올바른 괄호의 갯수(프로그래머스-level4)

안녕하세요 강민성입니다.

이번에는 처음으로 level4 에 도전했는데요,

관련된 개념을 한 번 본 적이 있어서 level 4 치고는 쉽게 풀 수 있었습니다.

그러면 문제 부터 보시겠습니다.

[ 문제 ]

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다.

 )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다.

 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를

 반환하는 함수 solution을 완성해 주세요.

제한사항

괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

입출력 예

n	result
2	2
3	5

입출력 예 설명

입출력 예 #1

2개의 괄호쌍으로 [ (()), ()() ]의 2가지를 만들 수 있습니다.

입출력 예 #2

3개의 괄호쌍으로 [ ((())), (()()), (())(), ()(()), ()()() ]의 5가지를 만들 수 있습니다.

저는 문제가 주어지면 종이와 펜을 꺼내서 손으로 써보는 편 입니다.

n=1 일 때 부터 규칙이 어느정도 보일때까지 직접 계산을 해보는데 이 경우에는 

n이 5만 되도 직접 카운팅하는게 상당히 힘들었습니다.

 

괄호가 다음과 같이 나타나고 각각의 경우를 세주면

n = 1 ) 1개

n = 2 ) 2개

n = 3 ) 5개

n = 4 ) 14개

n = 5 ) 42개

다음과 같습니다.

규칙을 찾아보려고 했지만 실패하고 결국 알고 있던 개념을 이용 하였는데

바로 '카탈랑 수' 입니다.

카탈랑 수에 대해 먼저 알아보도록 하겠습니다.

카탈랑수는 조합수학에서 빈번하게 등장하는 수열의 하나로,

(0,0) 에서 (n,n)까지 격자점을 지나는 최단거리의 경로 중에서 직선 y=x  를 넘지 않는 경우의 수를 말합니다.

경로의 수를 한 번 표시해보면

다음과 같습니다.

각 자리의 숫자는 좌측 하단 1 부터 시작해서 그 지점같이 갈 수 있는 최소경로를 의미하고

즉 카탈랑 수의 정의에 따라 대각선에 빨간색 숫자들은 카탈랑 수가 됩니다.

이 수들의 일반식은

다음과 같습니다.

그러면 어떻게 해서 다음과 같은 일반식이 만들어지는 지 알아보겠습니다.

먼저 위에서 말했듯이 격자점을 이용할 건데

(0,0) 에서 (n,n)까지 갈 수 있는 모든 방법의 수에서 y=x를 넘어가는 방법의 수를 빼도록 하겠습니다.

<  (0,0) 에서 (n,n)까지 갈 수 있는 모든 방법의 수  >

이를 구하는건 생각보다 간단합니다.

고등학교 확률과 통계 에서도 대표적인 문제 중 하나 입니다.

x축으로 이동하는걸 X라고 표현하고, 

y축으로 이동하는걸 Y라고 표현한다면

(0,0) 에서 (n,n)까지 갈 수 있는 경우는 X가 n개, Y가 n개인 총 2n개를 일렬로 나열하는 경우와 같습니다.

즉, 같은 것이 있는 순열로    다음과 같은 경우의 수를  얻게 됩니다.

<  y=x를 넘어가는 방법의 수 >

y=x를 넘어가는 경로의 수를 구하면 경로는 무조건 아래 그림과 같이

 y=x+1 과 만나게 될 것입니다. (현재 파란색 선이 경로, 녹색선이  y=x+1 입니다. )

이 때 (0,0) 에서 부터 y =x +1 과 처음으로 만나는 점까지 즉, 하늘색 선을 

y = x 에 대칭시켜 빨간색 선을 만들어 줍니다.

그리고남아있는 경로인 하늘색을 평행이동하여 빨간색 선과 이어줍니다.

하늘색 선을 평행이동한 선을 분홍색으로 표시하였습니다.

이제 최종적으로 이어진 선을 생각해보면

(0,0) 에서 (n+1 , n-1) 까지 가는 경로가 됩니다.

x축으로 이동하는걸 X라고 표현하고,  y축으로 이동하는걸 Y라고 표현한다면

(0,0) 에서 (n,n)까지 갈 수 있는 경우는 X가 n+1개, Y가 n-1개인 

총 2n개를 일렬로 나열하는 경우와 같습니다.

마찬가지로 같은 것이 있는 순열로서

 다음과 같은 값을 얻게됩니다.

(0,0) 에서 (n,n)까지 갈 수 있는 모든 방법의 수에서 y=x를 넘어가는 방법의 수를 빼기로 했으니

구하고자 하는 경로의 수는 아래와 같습니다.

자 이제 카탈랑 수의 일반식을 찾았으니 이를 코드로 구현만 해주면 끝납니다.

# 내 풀이
 
def fac(n): # 우선 팩토리얼을 계산해주는 함수
 
    if n == 1: # n=1 일 때는 
 
        return 1 # 1을 return 하고
 
    return n* fac(n-1) # 그렇지 않을 때는 n에 fac(n-1)을
                       #  곱하는 방식으로 재귀적으로 계산
 
def solution(n): # 답을 구하는 함수
 
    return fac(2*n)/(fac(n+1) * fac(n)) # 카탈랑 수를 표현

카탈랑 수를 생각하는 건 어려웠지만 그 뒤로 코드로 구현하는 건 어렵지 않았습니다.

마무리

알고리즘 공부를 시작한 지 얼마 안되었지만

생각보다 수학적 개념들이 많이 쓰여서 놀랐습니다.

최근에 코딩에 재미를 들려서 수학공부를 하지않은 걸 반성하며...

글을 마치겠습니다.