[프로그래머스 Lv.2] 타겟 넘버

코딩테스트 연습 - 타겟 넘버

문제 설명

n개의 음이 아닌 정수들이 있습니다.
이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

✔️ 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

❓ 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

풀이

To-Do 리스트

1. 기본값으로 0을 넣은 리스트를 만든다.
2. 주어진 수를 이전에 넣어진 값을 더해 넣는다.
   단, 주어진 수의 양수와 음수를 두개를 넣는다.
3. 리스트에 현재 넣은 값으로 만든 리스트를 넣는다.
4. 해당 타겟 값이 나오는지 리스트 값을 확인한다.
   타겟값이 있다면 answer에 1를 더한다.
5. 주어진 리스트만큼 2-4를 반복한다.

결과

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Queue<Integer> que = new LinkedList<Integer>();

        que.add(0);
        for (int i = 0; i < numbers.length; i++) {
          Queue<Integer> tmp = new LinkedList<Integer>();

          for (int q : que) {
            tmp.add(q + numbers[i]);
            tmp.add(q + numbers[i] * -1);
          }
          que = tmp;
        }
        for (int q : que) {
          if (q == target)
            answer++;
        }
        return answer;
    }
}

알게 된 점

💥 다른 사람의 풀이를 보니 dfs(깊이우선탐색) 방식으로 풀었다.
💥 dfs방식은 하나씩 비교한다.

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

    int dfs(int[] numbers, int n, int sum, int target) {
        if(n == numbers.length) { 
        //number의 길이만큼(즉, 끝까지 다한 경우)
            if(sum == target) { 
            // 모든 값을 다 더한 경우에 target과 일치여부에 따라
                return 1;
            }
            return 0;
        }
        return dfs(numbers, n + 1, sum + numbers[n], target) 
               // numbers의 n+1번째 배열로 이동
               // 전체 결과값 += numbers의 n번째 배열 더함.
             + dfs(numbers, n + 1, sum - numbers[n], target);
               // numbers의 n+1번째 배열로 이동
               // 전체 결과값 += numbers의 n번째 배열 뺌.
    }
}