📌 문제

Lv1. 삼총사

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

✔️ 제한사항

• 3 ≤ number의 길이 ≤ 13
• -1,000 ≤ number의 각 원소 ≤ 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있습니다.

✏️ 입출력

1. 입출력 예 #1 : 문제 예시와 같습니다.
   
   
2. 입출력 예 #2 : 학생들의 정수 번호 쌍 (-3, 0, 3), (-2, 0, 2), (-1, 0, 1), (-2, -1, 3), (-3, 1, 2) 이 삼총사가 될 수 있으므로, 5를 return 합니다.
   
   
3. 입출력 예 #3 : 삼총사가 될 수 있는 방법이 없습니다.

💡 코드

✅ 첫 요소부터 차례대로 3개씩 더해가면서, 합이 0이면 카운트하고 아니면 이전 단계로 돌아가 그 다음 값을 더하고, ... 와 같은 로직을 수행하기 위해 백트래킹을 사용해서 풀어보았다!

dfs(number, idx, depth)는 배열 number와 이번 순서에 더할 idx, 지금까지 합한 인원 수 depth를 매개변수로 전달받는다. 첫 요소부터 더할 것이므로 main 메서드에서 dfs(number, 0, 1)으로 시작한다.

총합 total에 number[i]를 더하고, 재귀 함수 dfs(number, i+1, depth+1)을 호출한다. 이 때, 같은 인덱스를 두 번 더하면 안되므로 for문의 초기화 변수를 idx로 설정해야 한다. depth = 4가 되면 3명의 번호를 더했다는 뜻이므로 total이 0이면 cnt++를 수행하고 종료, 0이 아니라면 바로 종료시킨다. return문을 통해 이전 단계로 돌아오면 for문을 통해 그 다음 인덱스의 값을 더해주는데, 이 때 이번 인덱스의 값을 다시 빼줘야 총합이 누적되지 않고 새로운 결과를 만들 수 있다.

class Solution {
    
    static int cnt = 0;
    static int total = 0;
    
    public int solution(int[] number) {
    
        dfs(number, 0, 1);
        return cnt;
    }
    
    static void dfs(int[] number, int idx, int depth) {
        
        if(depth == 4) {
            if(total == 0) cnt++;
            return;
        }
        
        for(int i=idx;i<number.length;i++) {
            total += number[i];
            dfs(number, i+1, depth+1);
            total -= number[i];
        }
        return;
    }
}

✅ 삼중 for문으로도 생각보다 잘 돌아간다! 뭔가 시간 오래 걸릴 것 같아서 백트래킹으로 푼거였는데,, 걍 효율성 대비 공부했다고 생각해야지,,

class Solution {
    public int solution(int[] number) {
        
        int cnt = 0;
        
        for(int i=0;i<number.length;i++) {
            for(int j=i+1;j<number.length;j++) {
                for(int k=j+1;k<number.length;k++) {
                    if(number[i] + number[j] +number[k] == 0) cnt++;
                }
            }
        }
        return cnt;
    }
}