[Programmers] 타겟 넘버

문제

• 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165
• 사용언어: java
• IDE: IntelliJ
• 알고리즘: 깊이 우선 탐색(DFS)

풀이

import java.util.Arrays;

public class TargetNumberSolution {
    private int matchingTargetCount = 0;

    public int solution(int[] numbers, int target) {
        int answer = 0;
        validateInput(numbers, target);

        depthFirstSearch(numbers, 0, target, 0);
        answer = matchingTargetCount;
        return answer;
    }

    // 깊이 우선 탐색(DFS)
    private void depthFirstSearch(int[] numbers, int depth, int target, int sum){
        if(isLastNodes(numbers, depth)){
            if(target == sum) matchingTargetCount++;
            return;
        }
        depthFirstSearch(numbers, depth + 1, target, sum + numbers[depth]);
        depthFirstSearch(numbers, depth + 1, target, sum - numbers[depth]);
    }

    private boolean isLastNodes(int[] numbers, int depth) {
        return depth == numbers.length;
    }

    private void validateInput(int[] numbers, int target) {
        int numbersCount = numbers.length;
        if (numbersCount < 2 || numbersCount > 20) {
            throw new IllegalArgumentException("주어지는 숫자는 2개이상 20개 이하입니다.");
        }

        Arrays.stream(numbers).filter(number -> number < 1 || number > 50).forEach(number -> {
            throw new IllegalArgumentException("각 숫자는 1 이상 50 이하인 자연수입니다.");
        });

        if (target < 1 || target > 1000) {
            throw new IllegalArgumentException("타겟 넘버는 1 이상 1000 이하인 자연수입니다.");
        }
    }
}

테스트코드

import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.stream.Stream;

import static org.junit.jupiter.api.Assertions.assertEquals;

class TargetNumberSolutionTest {
    @ParameterizedTest(name = "입출력 예시로 테스트{0}")
    @MethodSource("provideTestCases")
    void test(int[] numbers, int target, int result) {
        TargetNumberSolution targetNumber = new TargetNumberSolution();
        assertEquals(result, targetNumber.solution(numbers, target));
    }

    private static Stream<Arguments> provideTestCases() {
        return Stream.of(
                Arguments.of(new int[]{1, 1, 1, 1, 1}, 3, 5),
                Arguments.of(new int[]{4, 1, 2, 1}, 4, 2)
        );
    }
}