[JAVA] 경우의 수
모 기업 코딩테스트를 치른후 순열과 조합에 취약하다는 것을 깨닫고 실습을 위해 코드 작성.
(사실 순열조합 뿐만이 아니라 모든 알고리즘 문제에 취약)
1. 경우의 수 출력
일단 변수(스위치) 5개가 있고, 변수가 0 또는 1의 값을 가진다고 할 때, 모든 경우의 수를 출력하는 코드를 작성했다.
|
public static void main(String[] args) {
printAllNumberOfCases(5);
}
/**
* 모든 경우의 수 출력
*/
public static void printAllNumberOfCases(int totalCount) {
printSingleCase(“”, 0, totalCount);
}
public static void printSingleCase(String str, int position, int totalCount) {
if (position == totalCount) {
System.out.println(str);
return;
}
position++;
printSingleCase(str + “0”, position, totalCount);
printSingleCase(str + “1”, position, totalCount);
}
|
결과는 아래와 같다.
|
00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
|
2. 경우의 수 ArrayList 로 가져오기
위 코드는 System.out.println으로 곧바로 출력한다.
이 경우 데이터를 재활용할 수 없으므로 ArrayList로 가져오는 코드를 작성했다.
|
public static void main(String[] args) {
ArrayList<String> caseList = getAllNumberOfCases(5);
System.out.println(caseList);
}
/**
* 모든 경우의 수 어레이리스트로 반환
*/
public static ArrayList<String> getAllNumberOfCases(int totalCount) {
ArrayList<String> caseList = new ArrayList<String>();
getSingleCase(caseList, “”, 0, totalCount);
return caseList;
}
public static void getSingleCase(ArrayList<String> strList, String str, int position, int totalCount) {
if (position == totalCount) {
strList.add(str);
return;
}
position++;
getSingleCase(strList, str + “0”, position, totalCount);
getSingleCase(strList, str + “1”, position, totalCount);
}
|
결과는 아래와 같다.
|
[00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111]
|