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

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

프로그래머스

 

 

⭐️ 중요 포인트

DFS로 풀면 풀리는 간단한 문제였다. 다만 

        ret += recursion(idx + 1, sum + sNumbers[idx]);
        ret += recursion(idx + 1, sum - sNumbers[idx]);

이 부분에서 조금 해맸다. 처음에 조합 가능한 모든 경우의 수를 찾는 줄 알았다. 그래서 저 부분을 for문으로 감싸서 특정 숫자를 더하거나 빼지 않는 부분까지 포함되어있다.

다시 말하면 순서를 지키며 뒤에 숫자를 건너뛸 수도 있다...

그림 그려가며 풀어보기!..

 

class Solution {
    
    static int cnt;
    static int[] sNumbers;
    static int sTarget;
    static int answer;
    
    static void init(int[] numbers, int target) {
        answer = 0;
        cnt = 0;
        sNumbers = numbers;
        sTarget = target;
    }
    
    static int recursion(int idx, int sum) {
        
        if (idx == sNumbers.length) {
            if (sum == sTarget) {
                return 1;
            }
            return 0;
        }
        
        int ret = 0;
        
        ret += recursion(idx + 1, sum + sNumbers[idx]);
        ret += recursion(idx + 1, sum - sNumbers[idx]);
        
        return ret;
    }
    
    public int solution(int[] numbers, int target) {
        init(numbers, target);
        
        answer = recursion(0, 0);
        
        return answer;
    }
}

 

 

<잘못짠 코드 + gpt 도움 받아서 완성해서 해결은 되지만 매우 비효율적인 코드>

-> 이렇게 해도 풀리긴 풀린다 다만, 쓸데없이 중복되는 반복되는 경우(ex. 1, 2, 4, 5)를 거르지 못하고 모든 경우의 수 중에서 5개를 선택한 것 중에 target에 도달한 것만 1로 반환하기 때문에 속도가 많이 느리고, 문제의 의도와 다르게 풀린다.

class Solution {
    
    static int cnt;
    static int[] sNumbers;
    static int sTarget;
    static int answer;
    
    static void init(int[] numbers, int target) {
        answer = 0;
        cnt = 0;
        sNumbers = numbers;
        sTarget = target;
    }
    
    static int recursion(int idx, int sum, int usedCount) {
    if (usedCount == sNumbers.length) {
        if (sum == sTarget) {
            return 1;
        }
        return 0;
    }

    int ret = 0;

    for (int i = idx; i < sNumbers.length; i++) {
        ret += recursion(i + 1, sum + sNumbers[i], usedCount + 1);
        ret += recursion(i + 1, sum - sNumbers[i], usedCount + 1);
    }

    return ret;
}
    
    public int solution(int[] numbers, int target) {
        init(numbers, target);
        
        answer = recursion(0, 0, 0);
        
        return answer;
    }
}