[알고리즘]카탈란 수 구하기

---

---

# 문제

정수 n이 주어지면, n개의 여는 괄호 "("와 n개의 닫는 괄호 ")"로 만들 수 있는 

괄호 조합을 모두 구하시오. 

(시간 복잡도 제한 없습니다).

<예제>

Input: 1

Output: ["()"]

Input: 2

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

Input: 3

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

-------------------

해당 문제는 카탈란 수를 프로그래밍 화 시키라는 것이다.

처음 "("값을 0으로 잡고 ")"값을 1로 잡은 다음

맨 처음을 "("로

맨 끌을 ")"로 고정 시킨다음

그 사이의 값을 경우의 수로 만들려고 했지만

위의 예제같은 Output이 나오지 못했다.

그래서 결국 계속 고민했지만

해결법이 잘 안떠올라서 구글링을 해 보았고 아래와 같은 답변을 얻을 수 있었다.

# 코드

import java.util.ArrayList;
import java.util.List;
 
/*
정수 n이 주어지면, n개의 여는 괄호 "("와 n개의 닫는 괄호 ")"로 
만들 수 있는 괄호 조합을 모두 구하시오. 
(시간 복잡도 제한 없습니다).
*/
public class Main {
    public static void main(String[] args) {
        List<String> Result = new ArrayList<String>();
        // 재귀 함수를 통해서 값을 호출
        int Count = 0;
        solution(Result, "", 0, 0, 3, Count);
        
        for(String data: Result){
            System.out.println(data); //콘솔 출력
        }
    }
     
     
    public static void solution(List<String> Result, String cur, int open, 
                                int close, int n, int Count) {
 
        // 한 결과값 문자열의 길이는 무조건 N * 2 가 된다.
        // 때문에 N * 2 가 될 때 마다 값을 입력시킨다.
        if(cur.length() == n * 2) {
            Result.add(cur.toString());
            return;
        }
         
        // 열린 괄호의 수가 n보다 무조건 작아야 함
        if(open < n) {
            solution(Result, cur + "(", open + 1, close, n, ++Count);
        }
         
        // 열린괄호 만큼 닫힌괄호도 존재해야함
        if(close < open) {
            solution(Result, cur + ")", open, close + 1, n, ++Count);
        }
         
    }
}
 

# 느낀점

조합이나 순열같은 경우 재귀함수를 이용해야 

코드가 간결해지고 개발자도 편해지는거 같다.

재귀함수를 자주 사용해야겠다.

# 마무리

만약 틀린점이나 설명이 엉성한 부분이 존재하면 댓글로 알려주세요.

빠른 처리 하도록 하겠습니다.

티스토리 앱으로는 댓글 이용이 불가능 하므로 웹 브라우저로 봐 주세요

(URL : http://junprogramer.tistory.com/)

읽어주셔서 감사합니다.