[프로그래머스, Java] 타겟 넘버

사진을 클릭하면 해당 문제로 이동

⭐ 아이디어

💡풀이 1

- 재귀 풀이

class Solution {
    public int solution(int[] numbers, int target) {
        return sumCount(numbers, target, 0, 0);
    }

    int sumCount(int[] numbers, int target, int index, int sum) {

        if(index == numbers.length) {
            if(sum == target) {
                return 1;
            }
            return 0;
        }

        return sumCount(numbers, target, index + 1, sum + numbers[index])
               + sumCount(numbers, target, index + 1, sum - numbers[index]);
    }
}

💡풀이 2

- 재귀 없이 dfs 풀이

import java.util.ArrayDeque;
import java.util.Deque;

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

        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[]{0, 0}); // sum, index

        while(!stack.isEmpty()) {
            int[] current = stack.pop();
            int sum = current[0];
            int index = current[1];

            if(index == numbers.length) {
                if(sum == target) {
                    answer++;
                }
            } else {
                stack.push(new int[]{sum + numbers[index], index + 1});
                stack.push(new int[]{sum - numbers[index], index + 1});
            }
        }

        return answer;
    }
}

---

 

GitHub - okjunghyeon/Programmers_CodingTest: 프로그래머스 관련 코딩테스트 문제를 풀이한 저장소입니다.