기초CS/알고리즘
[프로그래머스] 알고리즘 연습 문제 : 타겟 넘버 (자바/JAVA)
H!GHR
2019. 9. 7. 11:41
https://programmers.co.kr/learn/courses/30/lessons/43165?language=java
코딩테스트 연습 - 타겟 넘버 | 프로그래머스
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이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘
programmers.co.kr
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
static int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, target, 0);
return answer;
}
public static void dfs(int[] numbers, int target, int node) {
if(node == numbers.length) {
int sum = 0;
for(int num : numbers) {
sum += num;
}
if(sum == target) {
answer++;
}
} else {
numbers[node] *= 1;
dfs(numbers, target, node+1);
numbers[node] *= -1;
dfs(numbers, target, node+1);
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
DFS, BFS에 대한 개념을 먼저 익히고 푸는게 좋은듯 싶다
(라고 상상함 하지만 어림도 없지ㅋㅋ 좀 더 익숙해지는 연습을 해야겠다...)
DFS는 stack, 재귀함수로 구현할 수 있고,
BFS는 queue로 구현 가능하다
이제 저걸 코드로 풀어서 응용만 하면 되는데 쉽지 않았다 (뇌굳남, 뇌가 굳어버린 남자)
1) DFS를 활용해 해당 node의 숫자를 (+), (-)로 배열에 넣어준다. (Tree로 보면 한쪽엔 (+), 다른쪽엔 (-))
2) node가 해당 배열까지 탐색했다면, numbers 배열을 다 더한다.
3) target과 비교해서 일치하면 카운트 +1, 아니면 다시 탐색 후 반복