[알고리즘] 프로그래머스 삼총사

프로그래머스 문제 링크

My Solution / Try

• 삼중 반복문을 돌며 더해서 0이 되는 값을 찾는다.
• 해당 인덱스 요소를 중복해서 더할 순 없으니(찾을 필요  X) 시작 인덱스는 1씩 증가하고,
  마지막 인덱스는 1씩 감소해서 비교한다

function solution(number) {
    let result = 0    
    for(let i=0; i < number.length-2; i++) {
        for(let j=i+1; j < number.length-1; j++) {
            for(let k=j+1; k < number.length; k++) {
                if(number[i] + number[j] + number[k] === 0) {
                    result++
                }
            }
        }
    }    
    return result
}

Advanced Solution

• 깊이우선탐색(DFS)를 활용한 풀이
• 알고리즘 유형 학습 후 이해가 필요

function solution(number) {
  let check = Array.from({ length: number.length }, () => false);
  let result = 0;
  const DFS = (idx, cnt) => {
    if (cnt === 3) {
      let SUM = 0;
      check.map((v, i) => {
        if (v === true) SUM += number[i];
      });
      result += SUM === 0 ? 1 : 0;
    }
    for (let i = idx; i < number.length; i++) {
      if (check[i] === true) continue;
      check[i] = true;
      DFS(i, cnt + 1);
      check[i] = false;
    }
  };
  DFS(0, 0);
  return result;
}