2틀에 걸쳐 풀고싶던 문제를 풀고있다.
문제의 핵심은 배열의 모든 조합을 추출 하는 것인데
재귀함수라는것을 사용하면 더 간단하고 쉽게 해결 할 수 있다고 한다.
재귀함수란 자기 자신을 불러오는 함수인데
무한루프에 빠지지 않기 위해 탈출값을 잘 설정하고 (위와 같은 문제라면 만약 배열에서 3개의 함수를 무작위로 뽑고 싶다면 현재의 배열에 3개가 뽑히면 탈출)
나머지는 함수를 돌려서 원하는 값을 얻어야 하는 방법이다.
보통은 팩토리얼로 예시를 들어주는데 여기까진 들으면 이해가 가는데 내가 지금 하는 작업에 응용하기가 쉽지가 않다.
내가 풀려던 문제는 배열에서 3개뽑는 모든 조합을 만든후 조합 숫자들을 더해 0이 되는 경우의 수를 구하는 문제였다.
이를 위해 접근한 방식은
// 필요한것 number 안의 숫자의 모든 조합을 r개씩만
// -2 3 0 (1 2 3)
// -2 3 2 (1 2 4)
// -2 3 -5 (1 2 5)
// -2 0 2 (1 3 4)
// -2 0 -5 (1 3 5)
// -2 2 -5 (1 4 5) ... (3 4 5)
// (3 4 5) 에서 3은 number.length==5 - (r-1 ==2)
// 4는 number.length -1
// 5는 number.length
// 이런식으로
// 이것으로 list를 만들고
// list 의 한 행의 모든 숫자를 더했을 시 0 이되면
// count++
// 모든 숫자의 조합을 어떻게 만들 것인가
// list
// List list = new arrayList<>;
// list 를 만들것인가 2차원 배열을 만들것인가
// 재귀함수를 사용해보자
// > 기준이되는 숫자는 number.length와 r 두개
// 일단 for 문으로 만들어보자
이런 방식으로 접근해보았다.
재귀함수를 사용해보고 싶었지만 뜻대로 풀리지 않아 포기하고 for문을 돌려 완성했다.
public static void main(String[] args) {
int[] number = {-2, 3, 0, 2, -5};
int answer = 0;
int r = 3;
List<List<Integer>> list = new ArrayList<>();
int n = number.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
List<Integer> innerList = new ArrayList<>();
innerList.add(number[i]);
innerList.add(number[j]);
innerList.add(number[k]);
list.add(innerList);
}
}
}
for (List<Integer> combination : list) {
if (combination.get(0) + combination.get(1) + combination.get(2) == 0) {
answer++;
}
}
System.out.println(answer);결국 원하는 값을 얻기는 했지만 뭔가 만족스럽지는 못했다.
