프로그래머스 타겟 넘버 JAVA

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

문제

정수가 주어졌을 때 이 정수들을 모두 한 번씩 사용해서 + - 연산을 통해 타깃과 같은 숫자를 만드는 경우의 수를 구하는 문제다.

조건

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

풀이

해당 문제를 보고 처음에 순열 조합을 이용해서 해결하려고 하던 중 dfs로도 가능할 거 같아서 dfs를 이용해서 해결하게 되었다. 심플하게 입력된 문자열 배열 길이만큼 깊이가 들어올 때까지 재귀를 돌리고 모두 사용했을 때 sum과 t가 같으면 카운트를 증가시켜준다 재귀 부분에서는 sum에 현재 깊이의 배열 값을 + -해주는 식으로 2번 재귀 호출을 해준다.

코드

class Solution {
	static int answer;
    public static int solution(int[] numbers, int target) {
        dfs(0,0,numbers,target); // 깊이, 합, numbers, target
        return answer;
    }

	private static void dfs(int index,int sum, int[] n, int t) { 
		if(index == n.length) { // 깊이랑 입력 numbers 길이가 같으면 sum과 target이 같은지 비교하고 카운트를 증가시키고 리턴한다
			if(sum == t)
				answer++;
			return;
		}
		dfs(index+1,sum+n[index], n, t); // +하는 경우
		dfs(index+1,sum-n[index], n, t); // -하는 경우
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드