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