(JAVA) 올바른 괄호의 갯수

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

프로그래머스

풀이

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

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

 

"(", 열린 괄호로 시작하여 나올 수 있는 괄호 조합들을 하나씩 탐색하는 것을 DFS 알고리즘을 사용하여 풀이하였다.

열린 괄호의 수를 open, 닫힌 괄호의 수를 close라고 하고, 아래와 같은 종료 조건들을 가지는 DFS를 통해 가능한 조합의 수를 구할 수 있었다.

 

1. 열린 괄호의 수와 닫힌 괄호의 수의 합이 n의 2배가 되는 경우는 n쌍의 괄호쌍을 모두 사용한 조합이므로 DFS를 종료한다. 이 때, 만약 열린 괄호의 수와 닫힌 괄호의 수가 같은 경우라면 이는 올바른 괄호이기에 카운트한다.
2. 열린 괄호의 수보다 닫힌 괄호의 수가 더 많다면 올바르지 않은 괄호쌍이기에 탐색을 종료한다.

class Solution {
    int number = 0; // 올바른 괄호의 갯수를 저장할 변수
    public int solution(int n) {
        dfs(1, 0, n); // 열린 괄호를 하나 두고 DFS 시작
        return number;
    }
    
    public void dfs(int open, int close, int n){
        if (open + close >= 2 * n) { // n쌍의 괄호쌍을 모두 사용한 경우
            if(open == close) number++; // 열린 괄호와 닫힌 괄호의 수가 동일한 올바른 괄호쌍인 경우라면 카운트
            return; // DFS 종료
        }
        
        if (open - close < 0) return; // 닫힌 괄호의 수가 더 많으면, 올바르지 않은 괄호쌍이므로 종료
        
        dfs(open+1, close, n); // 열린 괄호 추가 후 DFS 시작
        dfs(open, close+1, n); // 닫힌 괄호 추가 후 DFS 시작
    }
}

 

위처럼 DFS 말고, n개 이전의 괄호쌍으로 만들 수 있는 올바른 괄호쌍의 수를 사용한 DP로도 해당 문제를 해결할 수 있다.

(JAVA) 올바른 괄호의 갯수