(Python, Java) 프로그래머스 - 타겟 넘버

08 Jan 2022 in Algorithm on Programmers, Level2

[문제 링크]

풀이

from itertools import product


def solution(numbers, target):
    units = [(-x, x) for x in numbers]
    answer = list(map(sum, product(*units)))
    return answer.count(target)

product 활용법을 모른다면 참고하자.
product는 데카르트 곱이므로 각각 선택하고 결과값을 map을 이용해 더한 뒤 count로 개수를 구해 반환했다.

Java 풀이

class Solution {
    int n;
    int[] result;
    int answer;

    public int solution(int[] numbers, int target) {
        answer = 0;
        n = numbers.length;
        result = new int[n];
        dfs(0, numbers, target);

        return answer;
    }

    private void dfs(int depth, int[] numbers, int target) {
        if (n == depth) {
            if (Arrays.stream(result).sum() == target)
                answer++;
            return;
        }

        result[depth] = numbers[depth];
        dfs(depth + 1, numbers, target);

        result[depth] = -numbers[depth];
        dfs(depth + 1, numbers, target);
    }
}