[코딩테스트연습]프로그래머스-[1차] 타겟 넘버 (Lv2)

📝 문제설명

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 이하인 자연수입니다.

🔍입출력 예시

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

---

📌 작성코드

import java.util.*;
import java.lang.*;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        int cnt = 1; //
        
        ArrayList<Integer> arr1 = new ArrayList(); //총 경우의 수를 더한 값들이 저장될 변수
        
        arr1.add(numbers[0] * -1); //초기값
        arr1.add(numbers[0]); //초기값
        
        while(true) {
            ArrayList arr2 = new ArrayList(); //총 경우의 수에 현재 경우의 수들을 계산해 저장할 변수
            int arr1Len = arr1.size();
            
            for(int r=0; r<2; r++) {
                numbers[cnt] = numbers[cnt] * (-1); 
                for(int i=0; i<arr1Len; i++) {
                    arr2.add(arr1.get(i).intValue() + numbers[cnt]);
                }
            }
            arr1 = arr2; 
            if(cnt >= numbers.length-1) { //모든 배열을 다돌면
                break;
            } else {
                cnt++;
            }
            
        }
        
        for(int i=0; i<arr1.size(); i++) {
            if(arr1.get(i) == target) answer++;
        }
        
        return answer;
    }
}

💯Review

모든 경우의 수를 구해서 더한 후, 그 값들을 target값과 비교를 하는 방법으로 풀었다.
배열에 있는 값들은 -값 붙거나 +값들이 붙은 값들 밖에 나오지않는다. 그러므로 경우의수는 
n^(배열의길이)가 된다.

[4, 1, 2, 1] 기준으로 설명
1. arr1변수의 초기값으로 배열 맨 앞에 값을 넣어준다.
//arr1=(4, -4)

2. arr1의 모든값과 numbers[cnt]값과  -numbers[cnt]값을 더한 값들을 arr2에 저장한다.
//arr1=(4, -4)
//arr2=(5, 3, -3, -5)

3. arr2를 arr1의 넣어주고, arr2초기화
//arr1=(5, 3, -3, -5)
//arr2=()

4.이 과정을 반복하여 모든 경우의 수를 찾고, target과 비교한다.

🧾출처

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