[프로그래머스 lev2/JS] 타겟 넘버

문제 출처

프로그래머스 lev2 - 타겟 넘버

문제

나의 풀이

1차 시도(실패)

op로 분기점을 주고 싶었는데 감이 안 잡힌다..

function solution(numbers, target) {
  let ch = Array.from({length:numbers.length}, () => 0);
  let answer = 0;
  let op = [true, false];

  function Sum (L, sum) {
    if (L>numbers.length) return;
    if (sum>target) return;
    if (sum<0) return;
    if (L===numbers.length && sum===target) {
      answer++;
    }
    else {
      for (let i=0; i<numbers.length; i++) {
        if (ch[i]==0) {
          ch[i]=1;
          for (let i=0; i<op.length; i++) {
            if (op[i]==true) {
              Sum(L+1, sum+numbers[i]);    
              ch[i]=0;
            }
            else {
              Sum(L+1, sum-numbers[i]);    
              ch[i]=0;
            }
          }
        }
        
      }
    }
  }
  Sum(0, 0);
  return answer;
}

console.log(solution([1, 1, 1, 1, 1], 3))

2차 시도(실패)

성능 고려하지 않고 ans에 배열들을 전부 넣어서 new Set으로 중복을 제거하고 풀려고 했더니 문제점을 발견했다.

단순히 op로 분기점을 나누니까 numbers를 전부 넣는 게 아니라 2개만 넣어도 -+로 나눠서 4개가 계산된다는 점이 문제였다.

2차원 배열에서 중복 제거하는 법
[...new Set(ans.join('|').split('|'))].map(v => v.split(',')).map(v => v.map(a => +a));

function solution(numbers, target) {
  let ch = Array.from({length:numbers.length}, () => 0);
  let answer = 0;
  let op = [true, false];
  let tmp = [];
  let ans = [];

  function Sum (L) {
    if (L==numbers.length) {
      // console.log(tmp)
      ans.push(tmp.slice());
    }
    else {
      for (let i=0; i<numbers.length; i++) {
        if (ch[i]==0) {
          ch[i]=1;
          for (let i=0; i<op.length; i++) {
            if (op[i]==true) {
              tmp[L] = -numbers[i];
              Sum(L+1);    
              ch[i]=0;
            }
            else {
              tmp[L] = +numbers[i];
              Sum(L+1);    
              ch[i]=0;
            }
          }
        }
        
      }
    }
  }
  Sum(0);
  console.log(ans);
  ans = [...new Set(ans.join('|').split('|'))].map(v => v.split(',')).map(v => v.map(a => +a));
  
  for (let i=0; i<ans.length; i++) {
    let sum = ans[i].reduce((a,b) => a+b);
    if (sum === target) answer++;
  }
  return answer;
}

console.log(solution([4, 1, 2, 1], 4))

3차 시도 (통과)

재귀 내 for문을 numbers로 도는 게 아니라 op로 순회할 수 있게 변경했다.
그리고 각 numbers의 자리를 고정하기 위해
tmp[L] = +-numbers[i]; 를 사용했다.

배열을 썼으므로 성능이 좋지 않다.

function solution(numbers, target) {
  let answer = 0;
  let op = [true, false];
  let tmp = [];

  function Sum (L) {
    if (L==numbers.length) {
      // console.log(tmp.slice())
      let sum = tmp.reduce((a,b) => a+b);
      if (sum === target) answer++;
    }
    else {
      for (let i=0; i<op.length; i++) {
        if (op[i]==true) {
          tmp[L] = +numbers[L];
          Sum(L+1);
        }
        else {
          tmp[L] = -numbers[L];
          Sum(L+1);
        }
      }
    }
  }
  Sum(0);
  return answer;
}

console.log(solution([4, 1, 2, 1], 4))

다른 풀이

아래 풀이 역시 분기점을 +냐 -냐 2개로 잡아서 푼 풀이다.

function solution(numbers, target) {
  let answer = 0;
  getAnswer(0,0);
  function getAnswer(x,value) {
      if(x<numbers.length){
          getAnswer(x+1,value + numbers[x]);
          getAnswer(x+1,value - numbers[x]);
      } else{
          if(value === target){
              answer++
          }
      }
  }
  return answer;
}

console.log(solution([4, 1, 2, 1], 4))