[프로그래머스] 삼총사

🔗문제로 이동 [삼총사]

이 문제의 핵심은 크게 아래와 같이 볼 수 있다.

1. 조합의 이해 → n개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우
2. depth 은 현재 인덱스로 생각하고 해당 인덱스를 선택할때와, 선택하지 않을때 모두 재귀함수로 탐색하여 값을 구한다. 이전에 본 값들은 고려대상이 아니기 때문에 depth 은 무조건 1씩 증가시킨다. depth == n 인 경우는 모든 인덱스를 확인 했기 때문에 retun 한다.
3. 조합 알고리즘 🍇

☑️ 문제풀이 (1)

3개의 수를 뽑았을때 sum() 함수를 호출해서 값을 구했다. 속도는 나쁘지 않았지만 코드를 조금 더 줄이고자 다시 풀어보았다.

class Solution {
    
    public static int n, answer;
    public static boolean[] visited;
    public static int[] arr;
    
    public int solution(int[] number) {
        arr = number;
        n = arr.length;
        visited = new boolean[n];
        
        bfs(0, 3);

        return answer;
    }
    
    public static void bfs(int depth, int r) {
        if(r == 0) {
            sum();
            return;
        }
        
        if(depth == n) return;
        
				// 선택했을때
        visited[depth] = true;
        bfs(depth + 1, r - 1);

        // 선택하지 않았을때 
        visited[depth] = false;
        bfs(depth + 1, r);
    }
    
    public static void sum() {
        int sum = 0;
        int cnt = 3;
        for(int i = 0; i < n; i++) {
            if(visited[i]) {
                sum += arr[i];
                cnt--;
            }
        }
				// 합이 0이고, 3개의 수를 더했을때 answer++
        if(sum == 0 && cnt == 0) answer++;
    }
}

✅ 문제풀이 (2)

재귀함수를 호출할 때, 선택된 값들의 합을 인자로 같이 보내주었더니 보다 깔끔한 코드가 완성되었다.

class Solution {
    
    public static int n, answer;
    public static boolean[] visited;
    public static int[] arr;
    
    public int solution(int[] number) {
        
        arr = number;
        n = arr.length;
        visited = new boolean[n];
        
        bfs(0, 0, 3);
        
        return answer;
    }
    
    public static void bfs(int depth, int sum, int r) {
        if(r == 0) {
            if(sum == 0) answer++;
            return;
        }
        
        if(depth == n) return;
        
        // 선택했을때 sum에 해당 인덱스의 값 더하기
        visited[depth] = true;
        bfs(depth + 1, sum + arr[depth], r - 1);
        
        // 선택하지 않았을때 sum 그대로 유지 
        visited[depth] = false;
        bfs(depth + 1, sum, r);
    }

}