프로그래머스 메뉴 리뉴얼 문제를 풀려했다.
조합(combination)을 사용해 문제를 풀어야 하는 것은 알겠으나 도저히 조합을 구현하는 코드를 만들 수 없었다.

출처 : 코딩테스트 연습 - 메뉴 리뉴얼 | 프로그래머스

---

1. 조합 (combination)

재귀함수를 사용하여 구현할 수 있다.
재귀함수는 봐도봐도 어렵다;;
천천히 읽어보면 알 것 같지만 구현하라면 할 수 없을거 같은 느낌이다.
블로그 검색을 통해 조합과 순열의 구현 방식을 알 수 있었다. 감사합니다!

기본 아이디어

시작
  1을 선택(고정)하고 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다.
  [1, 2, 3] [1, 2, 4] [1, 3, 4]
  2를 선택(고정)하고 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다.
  [2, 3, 4]
  3을 선택(고정)하고 -> 나머지 [4] 중에서 2개씩 조합을 구한다. 
  [] 
  4을 선택(고정)하고 -> 나머지 [] 중에서 2개씩 조합을 구한다.
  []
종료

위와 같은 일련의 과정을 통해 모든 조합을 찾을 수 있다.
들어오는 인풋 배열이 길어지든, 조합해야하는 요소가 늘어나든 상관없다.
배열의 처음부터 하나씩 고정하면서 나머지 뒤의 배열에 대해 조합을 구한 후 붙이면 되는 것이다...

재귀함수를 사용하여 계속해서 반복 될 일(조합을 구하는 코드)에 대해서 한번만 명시 해 놓고, 들어가는 인자(나를 뺀 나머지)를 바꾸어 주기만 하면 된다.

재귀함수의 구현

1️⃣ 재귀 종료 조건: 하나를 선택할 때에는, 모든 배열의 원소를 선택해서 리턴한다.

2️⃣ forEach 문으로, 배열의 모든 원소를 처음부터 끝까지 한 번씩 고정(fixed) 되도록 한다.

3️⃣ 고정(fixed)된 값의 나머지 배열에 대해서 조합을 구하도록 한다. 이 때, 선택하는 개수를 하나 줄인다.

4️⃣ 조합을 만들어온 결과에 fixed 고정된 값을 앞에 붙여서 리턴할 배열에 spread syntax 로 배열화 한 후에 리턴한다.

5️⃣ 2C3, 1C2 같이 선택하려는 개수가 많으면 빈 배열이 return 되기 때문에 위의 예에서 3과 4를 선택할 때에는 빈 배열이 돌와아서 최종 결과값에 포함되지 않는다.

 const getCombinations = function (arr, selectNumber) {
    const results = [];
    if (selectNumber === 1) return arr.map((el) => [el]); 
    // n개중에서 1개 선택할 때(nC1), 바로 모든 배열의 원소 return

    arr.forEach((fixed, index, origin) => {
      const rest = origin.slice(index + 1); 
      // 해당하는 fixed를 제외한 나머지 뒤
      const combinations = getCombinations(rest, selectNumber - 1); 
      // 나머지에 대해서 조합을 구한다.
      const attached = combinations.map((el) => [fixed, ...el]); 
      //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
      results.push(...attached); 
      // 배열 spread syntax 로 모두다 push
    });

    return results; // 결과 담긴 results return
};

2. 순열 (permutation)

순열은 순서가 중요하다.

fixed는 똑같이 돌려주되 조합할 나머지 배열을 설정을 다르게 해주면 위의 조합 구현 방식을 참고해서 쉽게 구현할 수 있다.

function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixer = v;
    const restArr = arr.filter((_, index) => index !== idx);
    const permuationArr = permutation(restArr, selectNum - 1);
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    result.push(...combineFixer);
  });
  return result;
};

---

3. 문제 풀이

function solution(orders, course) {
  var answer = [];
  var orderBox = [];

  function combination(arr, selectNum) {
    const result = [];
    if (selectNum === 1) return arr.map((v) => [v]);
    arr.forEach((v, idx, arr) => {
      const fixed = v;
      const restArr = arr.slice(idx + 1);
      const combinationArr = combination(restArr, selectNum - 1);
      const combineFix = combinationArr.map((v) => [fixed, ...v]);
      result.push(...combineFix);
    });
    return result;
  }

  course.forEach(course => {
    orders.forEach(order => {
      const food = combination(order.split(''), course).map(order => {

        return order.sort().join('');
      })

      orderBox.push(...food);
    })

    const candidate = orderBox.reduce((acc, cur) => {
      acc[cur] = (acc[cur] || 0) + 1;
      return acc;
    }, {});

    let maxOrderFood = [];
    let maxOrder = 0;
    for (let key in candidate) {
      if (maxOrder < candidate[key]) {
        maxOrderFood = [key];
        maxOrder = candidate[key];
      } else if (maxOrder === candidate[key]) {
        maxOrderFood.push(key);
      }
    }

    if (maxOrder >= 2) answer.push(...maxOrderFood);

    orderBox = [];
  })

  answer.sort();
  return answer;
}

• 재귀 함수 공부하기 좋은 블로그
  Chapter 1. 재귀(Recursion) : 개념과 기본 예제들 - 평생 공부 블로그 : Today I Learned‍ 🌙

---

출처 :[JS]순열,조합,중복순열 구하기
JavaScript로 순열과 조합 알고리즘 구현하기. 재귀, JavaScript Array Methods | by 춤추는 개발자 | Medium
JavaScript로 순열과 조합 알고리즘 구현하기