코딩테스트 #3(재귀함수)

#3

정수 n이 주어지면, n개의 여는 괄호 "("와 n개의 닫는 괄호 ")"로 만들 수 있는 괄호 조합을 모두 구하시오. (시간 복잡도 제한 없습니다).

예제)

Input: 1

Output: ["()"]

Input: 2

Output: ["(())", "()()"]

Input: 3

Output: ["((()))", "(()())", "()(())", "(())()", "()()()"]

문제3은 재귀함수와 관련된 문제이다. 세번째 문제인데 벌써부터 슬슬 한계가 오는 것 같다. 혼자 풀어보려했지만, 도저히 풀 수 없어서 답안을 참고했다. 답안지에서는 주로 답의 양이 많거나 조합을 구하는 경우는 재귀함수를 사용하면 된다고 나와있다. '누워서 읽는 알고리즘'에서 재귀함수는 세련된 기법이라고 하였다. (저자가 재귀함수를 좋아하는 것 같다.) 미적으로 아름답고 개발자로 하여금 보기쉬운 코딩 기법이라 말했으며 물론 단점은 성능을 꼽았다.. 코딩시 조심하여야 한다고 했다.

재귀함수를 사용하는 것은 아직 나에게 무척 어렵게 느껴지므로 연습이 많이 필요할 것 같다.

public static void main(String[] args) {
        List ans = new ArrayList();
        solution(ans, "", 0, 0, 3);
        for(String str : ans) {
            System.out.println(str);
        }
    }
    
    
    public static void solution(List ans, String cur, int open, int close, int n) {
        if(cur.length() == n * 2) {
            ans.add(cur.toString());
            return;
        }
        
        if(open < n) {
            solution(ans, cur + "(", open + 1, close, n);
        }
        
        if(close < open) {
            solution(ans, cur + ")", open, close + 1, n);
        }
        
    }

여기서 생각해야할 점은

몇개의 여는 괄호와 닫는 괄호를 썼는지에 대한 점이다. 이 괄호의 갯수가 필요한 이유는 "(" 가 없는 상태에서 ")"가 나온다면 정당한 쌍이 이루어 지지 않기 때문이다.

따라서 문자열을 추가 할 때,  닫는괄호 ")"의 수는 여는괄호 "(" 수보다 작아야 하는 조건이 필요하다.