[조합] 프로그래머스 level2 타겟넘버 자바 풀이

프로그래머스 타겟넘버 자바(java) 풀이

• Level 2
• BFS/DFS
• 타겟넘버
  
  
  

문제 정리

1. n개의 음이아닌 정수가 있다.
2. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다.
3. 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하여라
4. 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
5. 각 숫자는 1이상 50이하의 자연수 이다.
   
   
   

문제 풀이

이 문제가 프로그래머스에는 BFS/DFS로 분류되어 있지만 저는 조합을 이용하여 풀었습니다.
조합을 이용하여 모든 경우의 수를 따져주었습니다.
1,2,...len개 선택하는 경우 모두 따져주었습니다.

1. len(numbers의 개수) 개중 i개 선택하기
   예를들어 1개를 선택한다면 1개만 visited가 true로 될 것입니다.
   그러면 하나만 더하기하고 나머지는 빼기연산을 해줍니다.
   그러면 +1-1-1-1-1도 구할 수 있게됩니다.
   위 경우는 visited[0]만 true로 되어있는 경우입니다.
2. 위와 같은 방법으로 len개 중 1개, 2개.. len개 선택하는 방법을 통해 모든 경우의 수를 구해주었습니다.
3. 그렇게 계산한 값 sum이 target과 같다면 cnt를 1 증가시킵니다.
   
   
   

프로그래머스 level2 타겟넘버 자바 코드

	class Main {
	public static void main(String[] args) {
	int[] numbers = {1,1,1,1,1};
	int target = 3;
	System.out.println(solution(numbers, target));
	}
	static boolean[] visited;
	static int cnt;
	static int[] copy;
	static int len;
	public static int solution(int[] numbers, int target) {
	len = numbers.length;
	cnt = 0;
	// comb함수에서 사용하기 위해 static으로 뺴놓기
	copy = new int[len];
	for(int i=0; i<len; i++)
	copy[i] = numbers[i];
	// len개 중 1,...len개 선택하는 조합 모두 구하기
	for(int i=1; i<=len; i++){
	visited = new boolean[len];
	comb(0, i, len, target);
	}
	return cnt;
	}
	public static void comb(int start, int r, int n, int target){
	if(start == r){
	int sum =0; // 계산한 결과
	// 선택한 숫자는 +, 선택하지 않는 숫자는 - 계산
	for(int i=0; i<len; i++){
	if(visited[i])
	sum += copy[i];
	else
	sum -= copy[i];
	}
	// 계산 결과가 target과 같다면 cnt 증가
	if(sum == target)
	cnt++;
	return;
	}
	// 조합 찾기
	for(int i=start; i<n; i++){
	visited[i] = true;
	comb(i+1, r, n, target);
	visited[i] = false;
	}
	}
	}

view raw programmersTargetNumber.java hosted with ❤ by GitHub