[프로그래머스] 타겟 넘버 (JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

정수 배열 numbers, 양의 정수 target이 주어진다.

numbers의 정수들을 이용해 적절히 더하고 빼면서 target이 될수 있는 경우의 수를 반환하면 된다.

 

프로그래머스 측에서 분류한대로 bfs나 dfs 알고리즘을 사용해 푸는 문제다.

각각 알고리즘을 사용해 푸는 경우를 작성해 보았다.

 

DFS 사용

// 프로그래머스 깊이/너피 우선 탐색(DFS/BFS)
// 양의 정수의 배열 numbers, 양의 정수 타겟 넘버 target이 배개변수로 주어짐
// numbers의 수들을 적절히 더하고 빼서 만들수 있는 target의 방법의 수를 반환
import java.util.*;

class Solution {
    static int answer = 0;

    public int solution(int[] numbers, int target) {
        // dfs
        dfs(numbers, target, 0, 0);
        return answer;
    }

    // dfs - 재귀 사용
    public void dfs(int[] numbers, int target, int depth, int sum) {
        if (depth == numbers.length) {
            if (sum == target) {
                answer++;
            }
            return;
        }
        // 각각 더하고 빼줌
        // depth + 1을 해주면 즉시 + 1이 동작함.
        // depth++을 해주면 오류 발생. 현재 depth의 값을 사용한 후에 ++을 해주기 때문
        dfs(numbers, target, depth + 1, sum + numbers[depth]);
        dfs(numbers, target, depth + 1, sum - numbers[depth]);
    }
}

 

dfs를 사용하기 위해서 재귀함수를 이용했다.

dfs 함수의 매개변수엔 기존에 주어진 numbers, target 이외에도 depth(깊이)와 sum(합계)을 받도록 했다.

numbers의 크기와 depth가 일치하면 재귀를 멈춘다.

그리고 sum이 target과 일치하면 answer을 증가시킨다.

 

BFS 사용

// 프로그래머스 깊이/너피 우선 탐색(DFS/BFS)
// 양의 정수의 배열 numbers, 양의 정수 타겟 넘버 target이 배개변수로 주어짐
// numbers의 수들을 적절히 더하고 빼서 만들수 있는 target의 방법의 수를 반환
import java.util.*;

class Solution {
    static int answer = 0;

    public int solution(int[] numbers, int target) {
        // bfs
        bfs(numbers, target);
        return answer;
    }

    // bfs - 큐 사용
    public void bfs(int[] numbers, int target) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        // 깊이까지
        for (int i = 0; i < numbers.length; i++) {
            // 너비까지
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                int sum = queue.poll();
                // 무다무다 계속 넣어줌
                queue.add(sum + numbers[i]);
                queue.add(sum - numbers[i]);
            }
        }

        // 들어가있는거 모두 확인
        while (!queue.isEmpty()) {
            if (queue.poll() == target) {
                answer++;
            }
        }
    }
}

 

bfs는 큐를 사용해 해결했다. 큐는 빨대모양 FIFO 구조 방식이다.

먼저 초기값 0을 큐에 넣어준다.

 

이중 for문을 이용해 깊이만큼, 너비만큼 반복해준다.

큐에서 나오는 정수에 배열의 다음 정수를 빼고 더한 값을 큐에 넣어준다.

 

반복문을 마친 후엔 큐에 들어있는 정수들을 모두 확인한다.

이 과정에서 target과 같은 값의 정수가 존재하면 answer을 증가시킨다.