[level2] 타겟넘버

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

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

 

 

---

 

 

문제 설명

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

 

입출력예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

 

 

---

 

 

구현 순서

 

step1. 부분집합을 이용하여 0개~N개의 원소를 골라낸다.

private static void subset(int cnt, int N) {
    if(cnt==N) {			
        
        return;
    }
    checked[cnt] = true;
    subset(cnt+1, N);
    checked[cnt] = false;
    subset(cnt+1, N);
}

 

step2. 부분집합으로 골라낸(true인) 원소는 더하고, 남은(false인) 원소는 빼준다.

int sum = 0;
for(int i=0; i<N; i++) {
    if(checked[i]) sum+=num[i];
    else sum-=num[i];
}

 

step3. 더하고 뺀 총합이 target과 같다면 case를 추가해준다.

if(sum == T) how++;

 

step4. target과 같은 합이 몇번 나오는지 전체 경우를 세준다.

public static int solution(int[] numbers, int target) {
    num = numbers;
    T = target;
    how = 0;
    checked = new boolean[numbers.length];
    subset(0, numbers.length);

    return how;
}

 

 

구현 코드

import java.util.Arrays;
class Solution {
    boolean[] checked;
	int[] num;
	int T;
	int how;
	private void subset(int cnt, int N) {
		if(cnt==N) {			
			int sum = 0;
			for(int i=0; i<N; i++) {
				if(checked[i]) sum+=num[i];
				else sum-=num[i];
			}
			if(sum == T) how++;
			
			return;
		}
		checked[cnt] = true;
		subset(cnt+1, N);
		checked[cnt] = false;
		subset(cnt+1, N);
	}
	public int solution(int[] numbers, int target) {
        num = numbers;
        T = target;
        how = 0;
        checked = new boolean[numbers.length];
        subset(0, numbers.length);
        
        return how;
    }
}