[프로그래머스] 올바른 괄호의 갯수(Lv.4) - Java/자바

문제

링크

코딩테스트 연습 > 연습문제 > 올바른 괄호의 갯수 (Lv. 4)
정답률 28% (2023.05.15 기준)

 

문제 설명

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

 

제한사항

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

 

입출력 예

n	result
2	2
3	5

 

입출력 예 설명

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

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

 

풀이

DFS(Depth First Search - 설명) 탐색을 이용하여 해결할 수 있는 문제이다.
풀고 나서 다른 사람들의 풀이를 보니 카탈란 수로 푸는 경우도 많았다. 하지만 DFS로 풀면 정말 간단하게 풀 수 있다... 아마 레벨4로 지정된 이유가 카탈란 수로 푸는 경우 때문이 아닌가 싶다.

DFS는 재귀호출 방식이나 Stack 방식으로 풀 수 있는데 이 문제에서는 상대적으로 메모리를 덜 쓰고 코드가 간결한 재귀호출 방식으로 풀어보았다.

근데 사실 이 문제는 괄호의 탐색 순서가 중요하지 않고 올바른 괄호의 총 개수만 알면 되기 때문에 Queue를 이용한 BFS로 풀어도 결과가 동일하게 나온다고 한다. DFS건 BFS건 결국 탐색을 한다는 것은 동일하고 탐색 순서를 깊이 우선으로 가냐, 너비 우선으로 가냐의 차이가 있는 것 뿐이기 때문이다.

 

코드

class Solution {
    int answer = 0;
    
    public int solution(int n) {
        dfs(0,0,n);
        return answer;
    }
    
    public void dfs(int open, int close, int n){
        if(open > n || open < close) return;
        if(open + close == 2*n){
            answer++;
            return;
        }
        
        dfs(open+1, close, n);
        dfs(open, close+1, n);
    }
}

 

해결 과정

1. 재귀호출할 dfs 함수를 만든다.
   •  open : "("의 개수
   •  close : ")"의 개수
   •  n : 괄호쌍의 개수
2. dfs 함수에서 다음의 경우에는 탐색을 중단하고  return 처리한다.
   •  open 이   n 을 초과하는 경우: 괄호쌍의 개수가 n개이기 때문에, "(", ")" 괄호가 각 n개씩 사용되어야 한다.
   •  close 가  open 보다 큰 경우: 괄호가 열리지 않았는데 닫히는 것이 우선될 수 없다.
   •  open  + close가 2*n인 경우: 올바른 괄호가 완성되었으므로  return 처리하고  answer 값에 1을 더한다.
3.  return 처리되지 않은 경우  dfs 를 재귀 호출해 준다.
   • 다음 괄호로 "("가 나올 수도, ")"가 나올 수도 있기 때문에  open 에 +1을 해서 한 번,  close 에 +1을 해서 한 번씩 호출해 준다.
4.  solution  함수에서   dfs  함수를 호출한다.

 

실행 결과