문제

코드

// 처음 풀이
function solution(orders, course) {
    const ans = [];

    for(let i of course) {
        const obj = {};
        for(let m of orders) {
            if(m.length < i) continue;
            
            const res = combination(m.split('').sort(), i);
            res.forEach(el => obj[el] = obj[el] ? obj[el]+1 : 1)
        }
        
        const maxCount = Math.max(...Object.values(obj))
        if(maxCount >= 2) {
            Object.entries(obj).forEach(el => {
                if(el[1] === maxCount) ans.push(el[0])
            })
        }
    }
    
    function combination(arr, selectCount) {
        const result = [];
        
        if(selectCount === 1) return arr.map(x => [x])
        
        arr.forEach((el, i) => {
            const combinations = combination(arr.slice(i+1), selectCount-1);
            combinations.forEach(combi => result.push([el, ...combi].join('')))
        })
        
        return result
    }
    
    return ans.sort();
}


// join 뺀 조금 더 빠른 풀이
function solution(orders, course) {
    const ans = [];

    for(let i of course) {
        const obj = {};
        for(let m of orders) {
            if(m.length < i) continue;
            
            const res = combination(m.split('').sort(), i, '');
            res.forEach(el => obj[el] = obj[el] ? obj[el]+1 : 1)
        }
        
        const maxCount = Math.max(...Object.values(obj))
        if(maxCount >= 2) {
            Object.entries(obj).forEach(el => {
                if(el[1] === maxCount) ans.push(el[0])
            })
        }
    }
    
    function combination(arr, selectCount, fixed) {
        const result = [];
        
        if(selectCount === 1) return arr.map(x => fixed + x)
        
        arr.forEach((el, i) => {
            const combinations = combination(arr.slice(i+1), selectCount-1, fixed + el);
            combinations.forEach(combi => result.push(combi))
        })
        
        return result
    }
    
    return ans.sort();
}

// 훨씬 더 빠른 풀이긴 한데...해석을 못 하겠다..
function solution(orders, course) {
  const ordered = {};
  const candidates = {};
  const maxNum = Array(10 + 1).fill(0);
  const createSet = (arr, start, len, foods) => {
    if (len === 0) {
      ordered[foods] = (ordered[foods] || 0) + 1;
      if (ordered[foods] > 1) candidates[foods] = ordered[foods];
      maxNum[foods.length] = Math.max(maxNum[foods.length], ordered[foods]);
      return;
    }

    for (let i = start; i < arr.length; i++) {
      createSet(arr, i + 1, len - 1, foods + arr[i]);
    }
  };

  orders.forEach((od) => {
    // arr.sort는 기본적으로 사전식 배열
    const sorted = od.split('').sort();
    // 주문한 음식을 사전순으로 배열해서 문자열을 만든다.
    // course에 있는 길이만 만들면 된다.
    course.forEach((len) => {
      createSet(sorted, 0, len, '');
    });
  });

  const launched = Object.keys(candidates).filter(
    (food) => maxNum[food.length] === candidates[food]
  );

  return launched.sort();
}

조합

function getCombinations(array, selectNum) {
  const answer = [];
  if (selectNum === 1) return array.map((value) => [value]);

  // 하나씩 fixedNum으로 삼기
  for (let i = 0; i < array.length; i++) {
    const temp = [...array];
    
    // i번째 인덱스 숫자가 fixedNum이 되면 그 부분까지 잘라냄
    temp.splice(0, i + 1);

    const combinations = getCombinations(temp, selectNum - 1);
    const attached = combinations.map((combination) => [array[i], ...combination]);
    answer.push(...attached);
  }

  return answer;
}

const array = [1, 1, 2, 3, 4];
const result = getCombinations(array, 3);

/* console
[
  [ 1, 1, 2 ], [ 1, 1, 3 ],
  [ 1, 1, 4 ], [ 1, 2, 3 ],
  [ 1, 2, 4 ], [ 1, 3, 4 ],
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 3, 4 ], [ 2, 3, 4 ]
]
*/

• 조합으로 모든 경우를 구하고 나온 값들을 obj에 넣어요!
• 그 중 가장 큰 수를 뽑아서 그 수와 일치하는 값을 ans.push해요!
• string을 배열로 바꿨다가 또 join을 하려니 조금 오래 걸리더라구요
• 그래서 매개변수로 fixed를 추가해 join 없이 완성했어요!

순열

function getPermutations(array, selectNum) {
  const answer = [];
  if (selectNum === 1) return array.map((value) => [value]);

  // 하나씩 fixedNum으로 삼기
  for (let i = 0; i < array.length; i++) {
    const temp = [...array];
    
    // fixedNum 을 제외한 배열을 가지고 순열 구하기
    temp.splice(i, 1);

    const permutations = getPermutations(temp, selectNum - 1);
    const attached = permutations.map((permutation) => [array[i], ...permutation]);
    answer.push(...attached);
  }

  return answer;
}

const example = [1, 2, 3, 4];
const result = getPermutations(example, 3);
console.log(result);

/* console
[
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 3, 2 ], [ 1, 3, 4 ],
  [ 1, 4, 2 ], [ 1, 4, 3 ],
  [ 2, 1, 3 ], [ 2, 1, 4 ],
  [ 2, 3, 1 ], [ 2, 3, 4 ],
  [ 2, 4, 1 ], [ 2, 4, 3 ],
  [ 3, 1, 2 ], [ 3, 1, 4 ],
  [ 3, 2, 1 ], [ 3, 2, 4 ],
  [ 3, 4, 1 ], [ 3, 4, 2 ],
  [ 4, 1, 2 ], [ 4, 1, 3 ],
  [ 4, 2, 1 ], [ 4, 2, 3 ],
  [ 4, 3, 1 ], [ 4, 3, 2 ]
]
*/

Set으로 순열 구하기

function getPermutations(array, selectNum) {
  const answer = new Set();
  if (selectNum === 1) return array.map((value) => [value]);

  // 하나씩 fixedNum으로 삼기
  for (let i = 0; i < array.length; i++) {
    const temp = [...array];
    
    // fixedNum 을 제외한 배열을 가지고 순열 구하기
    temp.splice(i, 1);

    const permutations = getPermutations(temp, selectNum - 1);

    const attached = permutations.map((permutation) => parseInt([array[i], ...permutation].join('')));
    attached.forEach((value) => answer.add(value));
  }

  const returnArray = [...answer].map((num) => num.toString().split('').map(s => parseInt(s)));
  return returnArray;
}

const example = [1, 1, 2, 3];
const result = getPermutations(example, 3);
console.log(result);

참고 사이트

• https://velog.io/@9ummy/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Level-2-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-JavaScript