[프로그래머스>LV4] 올바른 괄호의 개수(Kotlin/Python)

프로그래머스

 

1. 문제

[입력]

괄호 쌍의 개수 n

[결과]

n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환

 

2. 풀이

🌹 DP를 이용해 풀 수 있는 문제입니다.

 

DP를 어떻게 설정할 수 있을까요?

i개의 괄호로 만들 수 있는 올바론 괄호의 개수를 dp[i]라 할 때,

👇🏻 아래와 같이 구성될 수 있다는 것을 알 수 있습니다.

이 때, 한쪽은 반드시 ( ... ) 형태로 만들 수 있는 경우의 수만 계산해야 합니다.

👈🏻 왼쪽처럼 구별없이 경우의 수를 계산할 경우에는 중복되는 경우가 있을 수 있습니다. 😱 

때문에 👉🏻오른쪽과 같이 한쪽은 반드시 (...) 형태로 구성되도록 강제해야 합니다.

 

이를 위해 (...) 형태의 경우의 수만 저장하는 새로운 DP 배열이 필요하게 됩니다.

dp1 = [0] * (n+1)
dp2 = [0] * (n+1)

 

그렇다면 DP는 어떻게 계산하면 될까요?

dp2는 (...) 형태여야 하기 때문에 👇🏻 아래와 같이 계산할 수 있습니다.

dp2[i] = dp1[i-1]

 

dp1는 어떻게 구할 수 있을까요?

한쪽은 a개의 괄호쌍으로 만들 수 있는 올바른 괄호의 개수,

오른쪽은 b개의 괄호쌍으로 만들 수 있는 올바른 괄호의 개수 중 (...) 형태인 경우의 수이고

이 둘을 곱해주면 a / b 로 구성된 올바른 괄호의 개수를 만드는 경우의 수를 고할 수 있습니다.

dp1[i] = sum([dp1[i-k] * dp2[k] for k in range(i+1)])

 

위 내용들을 모두 합쳐 코드를 구현하면 아래와 같습니다.

3. 코드

Kotlin

class Solution {
    fun solution(n: Int): Int {
        val dp1 = IntArray(n + 1)
        val dp2 = IntArray(n + 1)
        dp1[0] = 1

        (1..n).forEach {
            dp2[it] = dp1[it - 1]
            dp1[it] = (0..it).sumOf { k -> dp1[it - k] * dp2[k] }
        }
        return dp1.last()
    }
}

Python

def solution(n):
    dp1 = [0] * (n+1)
    dp2 = [0] * (n+1)
    dp1[0] = 1
    
    for i in range(1,n+1):
        dp2[i] = dp1[i-1]
        dp1[i] = sum([dp1[i-k] * dp2[k] for k in range(i+1)])
    return dp1[-1]