[Programmers - JAVA] 타겟 넘버

 

programmers.co.kr/learn/courses/30/lessons/43165

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

 

문제

 

 

풀이

• 요새 프로젝트로 알고리즘을 한동안 안했더니 감을 잃어서 되찾으려 기초부터 다시 시작.
• 문제에 덧셈/뺄셈으로 타겟넘버를 만든다는 문구 존재.
• 더하는 방법 & 빼는 방법을 구현하기 위해 DFS를 활용.

 

과정

1.  매개변수로 numbers 배열 , target이 넘어온다.
2.  DFS호출 (배열, 타겟번호, 인덱스번호, 되는 경우의 수) -> DFS(numbers, target, 0, 0) 으로 호출
3. DFS에는 진행하는 동안 덧셈과 뺄셈을 각각 재귀호출.
4.  기저 조건은 numbers의 크기와 index가 일치하는 경우 -> 모든 자리에 대한 탐색 완료

 

 

알고리즘 지식

• DFS(깊이 우선 탐색)

 

 

제출 JAVA 코드

class Solution {
    public int solution(int[] numbers, int target) {
        int answer =  DFS(numbers, target, 0, 0);
        return answer;
    }
    public int DFS(int[] numbers, int target, int index, int num) {
		if (index == numbers.length) {
			return num == target ? 1 : 0;
		} else {
			return DFS(numbers, target, index + 1, num + numbers[index])
					+ DFS(numbers, target, index + 1, num - numbers[index]);
		}
	}
}

 

 

이해를 위한 로컬 실행 코드

package DFS_BFS;

import java.io.IOException;

public class 타겟넘버 {

	public static void main(String[] args) throws IOException {
		int[] numbers = new int[5];
		for (int i = 0; i < numbers.length; i++) {
			numbers[i] = 1;
		}
		int target = 3;
		System.out.println(new Solution().solution(numbers, target));
	}

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

		public int DFS(int[] numbers, int target, int index, int num) {
			if (index == numbers.length) {
				return num == target ? 1 : 0;
			} else {
				return DFS(numbers, target, index + 1, num + numbers[index])
						+ DFS(numbers, target, index + 1, num - numbers[index]);
			}
		}
	}
}