[매일프로그래밍] 4월 16일

4월 16일 문제 풀이는 조금 늦게 올리게 됐습니다. 다음 23일 문제도 최대한 빠르게 올리겠습니다.

4월 첫째주 포스팅 보기

4월 둘째주 포스팅 보기 

문제

---

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

특징

• 괄호는 여는 괄호의 개수보다 닫는 괄호의 개수가 많을 수 없다.
• 많은 경우의수를 요구하는 풀이다.

풀이

조합이나 경우의 수를 구하는 문제는 재귀함수로 풀이를 시도하는게 좋다고합니다. n개를 입력받아 경우의 수를 구할때 다음을 생각했습니다.

• 어떤 조건으로 경우의 수를 더해갈것인지
• 여는 괄호는 입력받은 숫자보다 많을 수 없다.
• 닫는 괄호는 여는 괄호보다 많은 수 없다.
• 어떤 조건으로 재귀함수를 끝낼 것인지
• 괄호의 수는 입력받은 수와 같다.

public  void Test(int input){

    List<String> list=new ArrayList<>();
    test(list,"",0,0,input);

    WLog.e("TEST","input="+input);
    for(int i=0;i<list.size();i++){
        WLog.e("TEST","i="+i+", list="+list.get(i));
    }

}

private  void test(List<String> list,String str, int open, int close, int input){

    if(str.length()==input*2){
        list.add(str);
        return;
    }

    if(input>open){
        test(list,str+"(",open+1,close,input);
    }

    if(open>close){
        test(list,str+")",open,close+1,input);
    }
}

수학시간에 특정 수열의 식을 구하기 위해선 예시들을 보고 식을 추측하는데, 해당 문제도 예를 보고 규칙을 찾아보면 조금 더 접근이 쉬울 것 같습니다.

해당 포스팅은 '매일프로그래밍'에서 출제된 문제와 풀이를 참고했습니다.  문제시 삭제하도록 하겠습니다.