[프로그래머스] 올바른 괄호의 갯수

문제 이해하기

n이 주어지면 그 중에 올바른 괄호쌍이 몇 개 있을 수 있는지 찾는 문제였다.

올바른 괄호쌍이란 ()()()와 같이 모두 닫친 괄호를 의미한다.

문제 해결 방법 설명하기

1.가지치기

n이 28(14 * 2)이기 때문에 완전탐색은 제한시간 내에 풀 수 없다. 따라서 시간을 줄이기 위해서 DP를 선택하던가 탐색하지 않아도 실패하는 경우를 발견해서 탐색을 줄여야 한다.

 

필자는 가지치기를 선택했고, 그 조건에 탐색 시점에서  남은 '(' 의 개수가 남은 ')'의 개수보다 많다면 탐색을 멈추도록 했다. 왜냐하면 닫친 괄호가 더 적게 남았다면  '(())))" 다음과 같은 상황이기 때문이다.

    if left_bracket > right_bracket:
        return 0

 

2. 완전탐색

또한 항상 남은 괄호가 정상적인 상황이라면 탐색을 진행해야 함으로 현재 자리에서 왼쪽 괄호를 선택하는 것과 오른쪽 괄호를 선택하는 것 모두 비교해봐야 한다. 

    if left_bracket:
        ans += search(left_bracket -1, right_bracket, n-1)
    
    if right_bracket:
        ans += search(left_bracket, right_bracket - 1, n-1)

코드

def search(left_bracket, right_bracket, n):
    ans = 0
    
    if left_bracket > right_bracket:
        return 0
    if left_bracket == 0 and right_bracket == 0:
        return 1
    
    if left_bracket:
        ans += search(left_bracket -1, right_bracket, n-1)
    
    if right_bracket:
        ans += search(left_bracket, right_bracket - 1, n-1)
    
    return ans

def solution(n):
    answer = 0
    
    total_bracket = n*2
    answer = search(n-1, n, total_bracket)
    
    return answer

if __name__ == "__main__":
    n = 3
    print(solution(n)) # 2

코드 리뷰

def solution(n):
    # 만약 n이 0이면 빈 문자열 하나만 가능하므로 1을 반환합니다.
    if n == 0:
        return 1

    # 동적 계획법을 위한 배열을 초기화합니다.
    dp = [0] * (n + 1)
    dp[0] = 1  # 0개의 괄호 쌍일 때는 빈 문자열 하나만 가능하므로 1을 설정합니다.

    # 1부터 n까지의 각 괄호 쌍에 대해 가능한 경우의 수를 계산합니다.
    for i in range(1, n + 1):
        # i개의 괄호를 만들기 위해서는 j개의 왼쪽 괄호와 i-1-j개의 오른쪽 괄호가 필요합니다.
        for j in range(i):
            # dp[j]는 j개의 괄호 쌍으로 만들 수 있는 괄호 문자열의 경우의 수입니다.
            # dp[i - 1 - j]는 i-1-j개의 괄호 쌍으로 만들 수 있는 괄호 문자열의 경우의 수입니다.
            # 따라서 dp[j] * dp[i - 1 - j]를 모두 더해줍니다.
            dp[i] += dp[j] * dp[i - 1 - j]

    # n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환합니다.
    return dp[n]

# 테스트
print(solution(2))  # 2개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수는 2입니다. "()()", "(())" 두 가지입니다.

배운점 정리하기

카탈란 수를 이용하면 DP로 변환이 가능하다.

https://m.blog.naver.com/pyw0564/221523147108

카탈란 수(Catalan number)