프로그래머스-코딩테스트 연습-깊이/너비 우선 탐색(DFS/BFS)-타겟 넘버
타겟 넘버
문제 설명
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 이하인 자연수입니다.
-
각 원소 앞에 붙을 수 있는 선택지는 2가지, +와 -
numbers.length가 n이면 총 가지수는 2^n
=>dfs로 정답 개수 체크하면 되겠다고 생각했다. -
도저히 그래프로 어떻게 구현할지 모르겠어서 이것 저것 찾아봤는데 인접행렬이나 인접리스트 형태로 구현하는건 비효율적이라고 생각했고 이진트리로 구현해야 한다는 결론에 이르렀다.
-
이진트리 DFS를 찾아보았으나 미궁속으로.... 이 코드가 제일 깔끔하고 좋아 보였으나 재귀로 구현한걸 이해하지 못했다.
-
결국 모범답안을 찾아보니 굳이 그래프 형식을 따르지 않아아도 되는 방법이었다. 결론은 너무 유형에 갇혀서 형식을 따르려고 애쓰지 말자! 대충 생각 흐름대로 풀면 된다.
ex. DFS로 구현할건데 정답 확인은 맨 마지막 노드에서만 하면 되네? 그럼 마지막 노드인지 확인해서 맞으면 정답 체크하고 아니면 재귀로 다음 노드 호출하면 되겠다. -
새로운 배열에 *±1을 하는게 아니라 numbers 배열을 맘대로 *±1을 해도 되는가 고민했다. 재귀호출인데 기존 배열의 값을 바꿔버리면 다음 호출 때 영향을 받아서 뒤죽박죽 되지 않을까?
=>결론은 괜찮다. 왜냐하면 재귀호출이 내 머릿속에서는 비동기적으로 동시에 호출이 좌르륵 일어나는 것 같지만 실제로는 윗줄의 재귀호출을 해서 그 안의 모든 재귀호출을 끝내야만 그 밑의*= -1과 아랫줄의 재귀호출을 할 수 있다. 그리고 만약 영향을 받아서numbers[k]가 음수 상태라고 하더라도*= -1하면 양수가 되니까 음수 계산을 먼저 하냐 양수 계산을 먼저 하냐의 차이일 뿐이다! -
삼항연산자 리턴하는 부분이 틀려서 삼항연산자의 문제인가
return의 문제인가answer++의 문제인가 디버깅을 했는데,answer을const로 작성한 문제였다. 아무리const가 안전하다고 해도let/const잘 구분해서 쓰자!
답안
function solution(numbers, target) {
let answer = 0;
function dfs(k){
if (k === numbers.length){
let sum = 0;
for(let i = 0; i < numbers.length; i++){
sum += numbers[i]
}
return sum === target ? answer++ : answer;
}
dfs(k+1);
numbers[k] *= -1;
dfs(k+1);
}
dfs(0);
return answer;
}