[JAVA] 단어 조합 가짓수 구하기

문제를 다시 적어보자면

A method public static TreeSet<String> generateStrings(char [] chSet, int length)

is used to generate all possible strings of the given length that can be formed with the characters given in chSet. The same character may be used more than once in a string. You can assume that all entries in chSet are pairwise different.

이번 문제는 예시에서 보여진 대로 문자와 숫자를 입력받고 숫자의 자릿수만큼 문자의 조합을 나타내는 것이다. 예를 들어 A,B,C와 3을 입력 받으면 AAA~CCC까지 출력이 되어야 한다. 그럼 총 3^3으로 27가지가 나오게 된다. 

처음에 이 문제를 받았을때는 별다른 생각이 없이 쉽다고만 생각했다. 

AAA, AAB, AAC이렇게 문자열을 하나씩 바꿔주면서 treeset에 저장하고 그걸 나중에 반환하면 되는거니까...  근데 생각이 처음부터 틀렸다. 멍청하게도 나는 AAA부터 시작을 한다고 당연하게 생각했는데 아니였다.

조합을 한다고 생각을 했어야 했다. 예시로 나온 3자리는 너무 기니 정말 간단하게 2자리로 시작을 해보자

만약 chSet이 {A,B}이고 length가 2로 주어졌다. 

그럼 우리가 기대하는 기대값은 

AA, AB, BA, BB이렇게 4개이다. 가장 초기단계인 AA는 그냥 배열의 첫번째 값이다. 반복문을 통해서 A와 A를 합친 거였다.

for (int i=0; i<chSet.length; i++) {

for (String arry:generateStrings(chSet,length-1)) {

set.add(String.valueOf(arry+chSet[i]));

}

}

이렇게 말이다. 

첫번째 반복문은 주어진 length만큼 길이값을 출력하기위해 존재하는 반복문이고 두번째 반복문이 단어를 조합 하는 반복문이다.

조건에선 String arry:generateStrings(chSet, length-1)을 통해서 재귀를 이용했다. 

generateStrings의 함수에서 리턴되는 값을 arry안에 넣고 treeset을 가르키는 변수 set에 집어넣는다. 이때 이렇게 되면 arry에는 마지막 값을 제외한 나머지 값들이 들어가게 된다. 

예시를 보면. AAA, AAB, AAC이렇게 끝자리가 먼저 바뀌고 그 다음엔 ABA, ABB, ABC이렇게 두번째자리가 바뀐뒤 고정되고 마지막 자리가 바뀐다. 따지고 보면 chSet[i]는 마지막 자리만 결정해 주는거고 앞에 2자리는 arry에서 정해지는 것이다.

물론 arry도 AA, AB,BA,BB이렇게 마지막자리가 바뀌면서 리턴이 된다. 이런 방식으로 set에 계속해서 저장을 해주는 거였다. 

전체적인 코드를 보게 되면

import java.util.TreeSet;

public class Exercise8 {

public static TreeSet<String> generateStrings(char[] chSet, int length) {

TreeSet<String> set = new TreeSet<String>();

if (length == 0)

{

set.add("");

return set;

}

for (int i=0; i<chSet.length; i++) {

for (String arry:generateStrings(chSet,length-1)) {

set.add(String.valueOf(arry+chSet[i]));

}

}

return set;

}

public static void main(String[] args) {

char[] characters = { 'A', 'B', 'C', 'D', 'E' };

int count = 0;

for (String sequence : generateStrings(characters, 4)) {

count++;

System.out.printf("%5d. %s%n", count, sequence);

}

}

}

main함수에서 %5d를 한 이유는 번호를 넣기 위해서이지 딱히 큰 의미는 없다.

내가 실험한 main함수에서는 a,b,c,d,e를 4자리로 나타내었다. 

기대값은 5^4 총 625개의 문자열이 나와야하는데 이걸 실행시켜 보면

 

이렇게 AAAA~EEEE까지 총 625개의 결과물이 나온다.

이 과제로 재귀함수를 한번더 이해하는 계기가 되었던것 같다. 

평소에 재귀함수를 이해하려고 종이에 써가면서 프로그램의 순서를 따라가려고 하지만 결국 이런 예제 하나가 이해하는데는 더 도움이 되는것 같다.