[21/10/04 KATA NINJA] Target Sum
코드
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
let count = 0;
DFS(0,0);
return count;
function DFS(current,level){
if(level === nums.length - 1){
if(target === current+nums[level]) count++;
if(target === current-nums[level]) count++;
}else{
if(validation(current+nums[level],level+1)) DFS(current+nums[level],level+1);
if(validation(current-nums[level],level+1)) DFS(current-nums[level],level+1);
}
}
function validation(next,start){
const sub = nums.slice(start).reduce((a,b)=>a+b)
return next-sub <= target && target <= next+sub
}
};
위 코드는 성능이 조금 구리다..
23% 성능.
메모이제이션을 사용하여 개선해보자.
개선 코드
var findTargetSumWays = function(n, t) {
const memo = {};
return DFS(t);
function DFS(target, level = 0) {
const hash = `${level},${target}`
if(memo[hash]){
return memo[hash]
}
if(level === n.length - 1){
// 레벨이 마지막 인덱스라면
// 1. 마지막 인덱스 값이 0이면서 현재 값이 0이라면 -> 2번 늘려준다 (+,-) 해도 같으므로
// 2. 마지막 인덱스 값이 0이 아니면서 다음 값과 현재 타겟 값을 절대 비교해주었을 때 같으면 -> 1회
// 3. 아니라면 0을 리턴
if(n[level] === 0 && target === 0 ) return 2;
if(n[level] === target || n[level] === -target) return 1;
return 0;
}
const res = DFS(target - n[level],level+1) + DFS(target+n[level],level+1)
memo[hash] = res;
return res;
}
};
메모이제이션을 추가해주었으나 더 느리다...?
아래 코드를 주석으로 변경해주어야
if(memo[hash]){
return memo[hash]
}
//if(memo[hash] !== undefined) return memo[hash] 로 바꾸어줘야함.
다음의 실행속도를 볼 수 있다. (why?)
dp로 풀면 더 빠르다.
다시 풀어보자.
var findTargetSumWays = function(nums, target) {
let total = nums.reduce((a,b)=>a+b);
const dp = [...new Array(nums.length+1)].map(()=>[...new Array(total*2+1)].map(()=>0));
// meaning : row -> 몇 개의 요소가 관여하였는가. column -> total을 기준으로 큰 index는 양수 작은 index는 음수이다. (관여된 요소의)총합을 의미한다.
if(total < Math.abs(target)){
// 다 더하거나 다 뺄때보다 오히려 타겟이 크면 찾을 수 없다.
return 0;
}
if(nums.length === 1 && Math.abs(total) === Math.abs(target)){
return 1;
}
if(nums.length === 1 && Math.abs(total) !== Math.abs(target)){
return 0;
}
dp[0][total] = 1; // what?
for(let r=0;r<nums.length;r++){
// dp 배열의 nums.length 로우에 값이 채워져있다. 종료되면
for(let c=0;c<dp[r].length;c++){
if(dp[r][c] !== 0){
// dp[r+1][c+nums[r]]가 몇개 나올수있는가
// dp[r][c]를 더 해준다.
// 이전까지 몇개가 나왔는지 더해준다.
dp[r+1][c+nums[r]] += dp[r][c];
dp[r+1][c-nums[r]] += dp[r][c];
}
}
}
return dp[nums.length][total + target];
};
Author And Source
이 문제에 관하여([21/10/04 KATA NINJA] Target Sum), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rat8397/211004-KATA-NINJA-Target-Sum저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)