[프로그래머스] 타겟넘버 (java)

📖 문제

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

---

🔑 풀이

✅ ArrayList<Integer> numbersAl: numbers[i]의 양수, 음수 순서로 저장

✅ ArrayList<ArrayList<Integer>> graph: numbers[i+1], numbers[i+1]*-1 저장 

1. numbers를 순회하며 numbersAl과 graph를 생성한다.
2. dfs를 첫 번째 원소의 양수, 음수 각각으로 실행한다.

✅ void dfs(int start, int sum, int target)

1. sum에 양수, 음수를 각각 더한 값으로 dfs를 각각 실행한다.
2. try catch문을 사용하여 start가 배열의 범위를 넘어서면(식이 끝나면) target과 sum을 비교한 후 종료한다 

import java.util.*;

class Solution {

	public static int answer;
	public static ArrayList<ArrayList<Integer>> graph;
	public static ArrayList<Integer> numbersAl;

	public static int solution(int[] numbers, int target) {
		answer = 0;

		graph = new ArrayList<>();
		numbersAl = new ArrayList<>();
		int idx1 = 2, idx2 = 3;
		for (int i = 0; i < numbers.length; i++) {
			// numbersAl 저장
			numbersAl.add(numbers[i]);
			numbersAl.add(numbers[i] * -1);

			// graph 저장
			ArrayList<Integer> al = new ArrayList<>();
			al.add(idx1);
			al.add(idx2);
			graph.add(al);
			graph.add(al);
			idx1 += 2;
			idx2 += 2;
		}

		// 첫 번째 원소의 양수, 음수 각각 dfs 실행
		dfs(0, numbersAl.get(0), target);
		dfs(1, numbersAl.get(1), target);

		return answer;
	}

	public static void dfs(int start, int sum, int target) {
		// try catch문을 사용하여 out of range라면 dfs 종료
		try {
			// 다음 수 더해서 dfs 실행
			int a = graph.get(start).get(0);
			int b = graph.get(start).get(1);
			dfs(a, sum + numbersAl.get(a), target);
			dfs(b, sum + numbersAl.get(b), target);
		} catch (Exception e) {
			// 합이 target과 같다면 answer 증가
			if (sum == target)
				answer += 1;
			return;
		}
	}
}

---

와 스스로 개멍청하다 생각하면서 풀었는데 진짜 난 멍청한 거였음

저렇게 푼 이유는요... dfs라면 응당 그래프를 생성해야지! 라는 생각에 음수 따로 양수 따로 저장했는데

그럴필요 없이..,, dfs할 때 sum에 더해주고 빼면 되는 거였네 ㅋ 왤케 머리가 굳엇지....

슬픈 밤이네요