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

programmers.co.kr/learn/courses/30/lessons/12929

코딩테스트 연습 - 올바른 괄호의 갯수

[문제 설명]

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.제한사항

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

입출력 예

nresult

n	result
2	2
3	5

입출력 예 설명

입출력 예 #1
2개의 괄호 쌍으로 [ (()), ()() ]의 2가지를 만들 수 있습니다.
입출력 예 #2
3개의 괄호쌍으로 [ ((())), (()()), (())(), ()(()), ()()() ]의 5가지를 만들 수 있습니다.

 

 

[풀이]

올바른 괄호의 짝 중에, '('로 시작했으면 ')'로 끝나는 성질을 이용해 ')'의 개수가 '('보다 많으면 올바르지 않은 식으로 간주하고, 이 모든 경우의 수를 dfs로 찾았다.

 

[코드]

    int count;
    
    public int solution(int n) {
        count = 0;
        
        dfs(0, 0, n);
        return count;
    }
    
    public void dfs(int left, int right, int n) {
        if(left < right) return;
        if(left == n && right == n) {
            count++;
            return;
        }
        
        if(left > n || right > n) return;
        
        dfs(left + 1, right, n);
        dfs(left, right + 1, n);
    }

프로그래머스 테스트 케이스 통과

느낀 점: 처음에 카탈란 수로 푸는 사람을 보고 힌트를 얻어 카탈란 수로 풀어보려고 했지만(재귀), 더 간단한 방법으로 푸는 사람을 보고 반성하며 dfs로 풀게 되었다..