[레벨1] 삼총사 - 자바스크립트에서 조합은 어떻게 구할까?

1. 프로그래머스 레벨 1 "삼총사"

https://school.programmers.co.kr/learn/courses/30/lessons/131705?language=python3 

프로그래머스

 

2. 파이썬에서 itertools로 조합을 구하여 풀이 성공

이 문제는 조합을 이용하여 경우의 수를 구해 풀이하면 되었다. 파이썬은 itertools라는 유용한 라이브러리를 가지고 있기 때문에 이를 이용하면 쉽게 풀 수가 있다. itertools는 "조합" 뿐만 아니라 "순열"도 구할 수 있다.

import itertools

# 첫번째 매개변수에는 이터러블한 객체를 넣어주고
# 두번째 매개변수에는 결과로 받고자하는 요소의 수를 넣어 준다.
perm = itertools.permutations(chars, 3)  # 순열
comb = itertools.combinations(chars, 3)  # 조합

😉 "순열"은 요소가 같더라도 순서(요소의 인덱스)가 다르면 다른 객체로 여긴다. 반면 "조합"은 순서와 상관없이 요소만 비교한다.

 

제출하여 성공한 코드는 다음과 같다.

import itertools

def solution(number):
    answer = 0
    result = list(itertools.combinations(number, 3))  # 조합
    for i in result:
        if sum(i) == 0:
            answer += 1
    return answer

print(solution([-2, 3, 0, 2, -5]))  # 2

 

3. 자바스크립트는 itertools가 없는데??

자바스크립트로도 코드를 작성해 봤다. 그런데 자바스크립트에는 itertools가 없어서 그것과 같은 역할을 하는 조합 함수를 만들었다. 해당 코드는 아래와 같다.

function combinations(arr, k) {
    const result = [];

    function backtrack(subset, start) {
      if (subset.length === k) {
        result.push([...subset]);
        return;
      }

      for (let i = start; i < arr.length; i++) {
        subset.push(arr[i]);
        backtrack(subset, i + 1);
        subset.pop();
      }
    }

    backtrack([], 0);
    return result;
  }

이 함수를 이용해 최종 제출한 코드는 다음과 같다.

function solution(number) {
  var answer = 0;

  function combinations(arr, k) {
    const result = [];

    function backtrack(subset, start) {
      if (subset.length === k) {
        result.push([...subset]);
        return;
      }

      for (let i = start; i < arr.length; i++) {
        subset.push(arr[i]);
        backtrack(subset, i + 1);
        subset.pop();
      }
    }

    backtrack([], 0);
    return result;
  }

  const result = combinations(number, 3);

  result.forEach((el) => {
    answer += el.reduce((acc, curr) => acc + curr, 0) == 0 ? 1 : 0;
  });

  return answer;
}

console.log(solution([-2, 3, 0, 2, -5]));