2021 KAKAO BLIND RECRUITMENT - 메뉴 리스트 (자바스크립트)

LV2. 메뉴리뉴얼

조합

JavaScript로 순열과 조합 알고리즘 구현하기 를 통해 조합에 대한 알고리즘을 공부했습니다.

const getcombination = (arr, selectNum) => {
  const result = [];

  if (selectNum === 1) return arr.map((element) => [element]);

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combination = getcombination(rest, selectNum - 1);
    const attached = combination.map((element) => [fixed, ...element]);

    result.push(...attached);
  });

  return result;
};

그렇게 된다면, selectNum 길이만큼의 조합이 전체 나온다.

sudo

1. 메뉴에 대한 조합을 구한다.

   초기에 selectNum은, 1부터 order[i].length 까지 구하려했지만 비효율 => course에 담긴 숫자만큼 돌아준다.

2. course를 반복문으로 돌면서 course와 length 가 일치하는 요소를 찾아준다.

3. 찾은 요소들에서 또 max 값을 구해서, max값과 일치하는 value 를 가진 요소만을 리턴해준다.

4. 정렬시켜준다.

풀이

const getcombination = (arr, selectNum) => {
  const result = [];

  if (selectNum === 1) return arr.map((element) => [element]);

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combination = getcombination(rest, selectNum - 1);
    const attached = combination.map((element) => [fixed, ...element]);

    result.push(...attached);
  });

  return result;
};

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

  let obj = new Map();

  for (let i = 0; i < orders.length; i++) {
    const order = orders[i].split("");
    for (let j = 0; j < course.length; j++) {
      //   // course에 담긴 length 만큼만 회전한다.
      const combination = getcombination(order, course[j]);
      combination
        .map((element) => element.sort().join(""))
        .forEach((element) => obj.set(element, (obj.get(element) || 0) + 1));
    }
  }

  for (let i = 0; i < course.length; i++) {
    const courseList = [];
    let max = 0;
    for (let [key, value] of obj) {
      if (key.length === course[i] && value >= 2) {
        courseList[key] = value;
        max = Math.max(max, value);
      }
    }

    for (let [key, value] of Object.entries(courseList)) {
      if (value === max) answer.push(key);
    }
  }

  return answer.sort();
}