문제
100/100 (2시간 반 소요)
기본적인 내용
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 함수를 작성해주세요.
추가 해석 필요한 부분
예시는 전부 1이지만 모든 배열은 순서를 고려하지않는다는 부분이 추가되어야한다.
중복허용 안된다. => -1 1 1 1 1에서 4번째 5번째가 바뀐 -1 1 1 1 1도 같은 거로 이해해야한다.
DFS 깊이 우선 탐색
전위순회
const D = (x)=>{
if(x>7) return;
else{
console.log(x);
D(x*2);
D(x*2+1);
}
}
D(1)
결과
1
2
4
5
3
6
7
전위순회를 통한 노드 값을 얻어낼 수 있다.
1 2 3 4 5 6 7
성공한 코드
function solution(numbers, target) {
let val=0,result=0;
const numbers_length = numbers.length;
return D(1,numbers_length,target,val,result,numbers);
}
const D = (x,numLength,target,val,result,numbers)=>{
if(x>Math.pow(2,numLength+1)-1) return result;
else{
if(x%2==0)
val+=numbers[Math.floor(Math.log2(x))-1]
else if(x%2==1 && x!=1)
val-=numbers[Math.floor(Math.log2(x))-1]
if(x > Math.pow(2,numLength) && target == val ){
result ++;
}
result = D(x*2,numLength,target,val,result,numbers);
result = D(x*2+1,numLength,target,val,result,numbers);
}
return result;
}코드분석
1)
let val=0,result=0;
const numbers_length = numbers.length;
return D(1,numbers_length,target,val,result,numbers);numbers의 크기를 담는
numbers_length와 계산값을 담는val, target과 맞으면 값을 추가하는result가 있다.
2)
const D = (x,numLength,target,val,result,numbers)=>{
if(x>Math.pow(2,numLength+1)-1) return result;
else{
...
}
}root노드인 1부터 시작해 갈래가 예를들어 배열이 5개면 5개의 갈래가 진행되어야 하므로 2의 6승 -1 (1~63) 까지 갯수가 있어야하므로
x > Math.pow(2,numLength+1)-1보다 큰것은 필요없으므로 result를 리턴시킨다.
- (조건절을 통해서 리턴하는 result도 중요하다 그냥
return ;할 경우 제대로 된 필요한 return 값 처리를 진행하기 어렵다)
3)
if(x%2==0)
val+=numbers[Math.floor(Math.log2(x))-1]
else if(x%2==1 && x!=1)
val-=numbers[Math.floor(Math.log2(x))-1]
if(x > Math.pow(2,numLength) && target == val ){
result ++;
}맨 아래 바닥노드까지 진행하는데 있어서 왼쪽노드는 +를 하고 오른쪽 노드는 -를 하므로 if else문을 작성하고 이때 첫번째노드가 1이므로 그때는 빼주는 조건도 추가작성한다.
x의 값이 진행하면서 바닥노드일때 (
x > Math.pow(2,numLength)) 그리고 그때 target과 계산한 val이 값이 같으면(target == val) 그때에 result값을 추가한다.
4)
result = D(x*2,numLength,target,val,result,numbers);
result = D(x*2+1,numLength,target,val,result,numbers);이는 아까 반복하는 전위순회와 같다 x의 값을 전위순회하는 역할을 한다.
그러면서 D함수를 통해 리턴한 값은 result가 되게 한다.
5)
return result;전부 끝나는 마지막에서 result의 값을 리턴하여 반환한다.
느낀점
DFS 알고리즘을 배울줄이야 학교에서 C++로 배울때 진짜 힘들었는데
js는 나은 것 같다.
출처의 블로그 덕분에 더 알아간다.
if 조건문 걸고 return 하는부분 에서 같은 값을 리턴해야 값이 보존된다
그냥return ;하면 제대로 원하는 결과 못얻는다.
출처
코드 혼자 짜기
1)
function solution(numbers, target) {
var answer = 0;
return answer;
}2)
function D(x,numbers,result){
if(x>Math.sqrt(2,numbers.length+1)-1) return result;
else{
}
return result
}
function solution(numbers, target) {
var answer = 0;
return answer;
}3)
function D(x,numbers,result){
if(x>Math.sqrt(2,numbers.length+1)-1) return result;
else{
if(x%2 == 0) val += numbers[Math.floor(Math.log2(x)-1]
else if(x%2 == 1 || x != 1) val -= numbers[Math.floor(Math.log2(x)-1]
result = D(x*2,numbers,result)
result = D(x*2+1,numbers,result)
}
return result
}
function solution(numbers, target) {
var answer = 0;
return answer;
}4)
function D(x,numbers,result,val){
if(x>Math.sqrt(2,numbers.length+1)-1) return result;
else{
if(x%2 == 0) val += numbers[Math.floor(Math.log2(x)-1]
else if(x%2 == 1 || x != 1) val -= numbers[Math.floor(Math.log2(x)-1]
if(val == target && Math.floor(Math.log2(x)) == numbers.length)
result++;
result = D(x*2,numbers,result,val)
result = D(x*2+1,numbers,result,val)
}
return result
}
function solution(numbers, target) {
var answer = 0;
return D(1,numbers,0,0);
}5)
function D(x,numbers,result,val,target){
if(x>Math.pow(2,numbers.length+1)-1) return result;
else{
if(x%2 == 0) val += numbers[Math.floor(Math.log2(x))-1]
else if(x%2 == 1 && x != 1) val -= numbers[Math.floor(Math.log2(x))-1]
if(val == target && Math.floor(Math.log2(x)) == numbers.length)
result++;
result = D(x*2,numbers,result,val,target)
result = D(x*2+1,numbers,result,val,target)
}
return result
}
function solution(numbers, target) {
var answer = 0;
return D(1,numbers,0,0,target);
}Math.sqrt => Math.pow로 수정
x%2 == 1 || x != 1 를 x%2 == 1 && x != 1 로 수정
Math.log2(x) 괄호 맞추기
target 매개변수 추가
