(JAVA) 올바른 괄호의 갯수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

풀이

난이도가 4인 문제임을 생각하면 코드가 매우 단순함을 확인할 수 있다.

코드 자체는 단순한데 문제 풀이를 위한 방법을 생각하는 것이 어려운 문제라고 생각할 수 있다.

 

n개 이전의 괄호쌍으로 만들 수 있는 개수를 활용하는 Dynamic Programming을 사용하여 풀이하였다.

 

예를 들어 괄호쌍 2개와 3개를 사용해 만들 수 있는 전체 올바른 괄호쌍의 개수를 계산해 보겠다.

우선 arr라는 배열에 dp를 위해서 이전의 결괏값들을 저장했다고 가정하겠다.

arr [0]에는 괄호 0쌍으로 만들 수 있는 올바른 조합의 개수를 1이라고 가정하고 저장하고, arr[1]에는 괄호 1쌍으로 만들 수 있는 올바른 조합은 () 하나 이므로 1을 저장한다.

괄호쌍 2개의 경우

(()), ()()가 괄호쌍 2개로 만들 수 있는 올바른 괄호쌍이기에 2라는 결과를 얻어내야 한다.

 

(())의 경우

([괄호쌍 1개로 만들 수 있는 올바른 조합]) * [괄호쌍 없음] = dp[1] * dp[0] = 1 * 1 = 1

 

()()의 경우

([괄호쌍 없음]) * [괄호쌍 1개로 만들 수 있는 올바른 조합] = dp[0] * dp[1] = 1 * 1 = 1

 

따라서 위 둘의 경우의 합인 2를 dp[2]에 저장한다.

괄호쌍 3개의 경우

((())), (()()), ()(()), (())(), ()()()가 괄호쌍 3개로 만들 수 있는 올바른 괄호쌍이기에 5라는 결과를 얻어내야 한다.

 

((())), (()())의 경우

([괄호쌍 2개로 만들 수 있는 올바른 조합]) * [괄호쌍 없음] = dp[2] * dp[0] = 2 * 1 = 2

 

(())()의 경우

([괄호쌍 1개로 만들 수 있는 올바른 조합]) * [괄호쌍 1개로 만들 수 있는 올바른 조합] = dp[1] * dp[1] = 1 * 1 = 1

 

()(()), ()()()의 경우

([괄호쌍 없음]) * [괄호쌍 2개로 만들 수 있는 올바른 조합] = dp[0] * dp[2] = 1 * 2 = 2

 

따라서 위의 모든 경우의 합인 5를 dp[3]에 저장한다.

 

위와 같은 방식으로 괄호쌍 n개 일 때의 올바른 괄호쌍의 수를 계산할 수 있다. 아래는 이를 코드로 구현한 것이다.

class Solution {
    public int solution(int n) {
        int[] arr = new int[n+1];
        arr[0] = 1; // 괄호쌍 0개로 만들 수 있는 올바른 괄호쌍의 갯수는 계산을 위해 1로 가정
        arr[1] = 1; // 괄호쌍 1개로 만들 수 있는 올바른 괄호쌍은 ()의 경우로 1개
        
        for (int i = 2; i <= n; i++){ // dp로 계산
            for (int j = 0; j < i; j++){
                arr[i] += arr[i - j - 1] * arr[j];
            }
        }
        
        return arr[n];
    }
}

위처럼 DP를 이용한 방법 말고도 여는 괄호의 수, 닫는 괄호의 수, 전체 괄호의 수를 가지고 DFS로 풀이할 수도 있다.

(JAVA) 올바른 괄호의 갯수