출처

https://school.programmers.co.kr/learn/courses/30/lessons/72411#

코드

function getCombinations(arr, selectNum) {
  const results = [];
  if (selectNum === 1) {
    return arr.map((value) => [value]);
  }
    
  arr.forEach((value, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, selectNum - 1);
    const attached = combinations.map((combination) => [value, ...combination]);
    results.push(...attached);
  });

  return results;
}

function solution(orders, course) {
    var answer = [];
    
    const flat = orders.join('')
    let set = new Set(flat)
    set = [...set].sort() // 오름차순 반환 위해서 sort
    
    for (const ele of course) {
        if (set.length < ele) continue
        const cbList = getCombinations([...set], ele) 
        // console.log(cbList)
        
        let map = new Map()
        
        for (const cb of cbList) {
            let cnt = 0
            
            for (let order of orders) {
                order = order.split('')
                // some) 조합의 요소를 돌면서 콜백이 true를 반환하면, true할당 & 즉시 종료됨. 다 돌때까지 true 안나오면 false 할당됨.
                let include = !cb.some(ele => !order.includes(ele)); 
                if (include) cnt ++
            }
            
            if (cnt>=2) map.set(cb, cnt)                       
        }
        
        if (map.size===0) continue
        
        map = [...map].sort((a,b)=>b[1]-a[1])
        // console.log(map)
        let maxV = map[0][1]
        
        map.forEach(ele=>{
            if (ele[1]===maxV) answer.push(ele[0].join(''))
        })
    }
    
    return answer.sort()
}

설명

• 손님들이 숫자가 담긴 course배열을 순회하면서 메뉴주문에 사용한 모든 알파벳의 조합을 구하고, 조건에 맞게 계산한 코드이다.
• 계산은 정확하지만 입력이 큰 케이스에 대해서 런타임 에러(시간초과)가 발생한다.
• 따라서, 각 손님의 order에서 조합을 생성하고 이를 계산하는 식으로 연산량을 줄여야 한다.

개선된 코드 (정답)

function getCombinations(arr, selectNum) {
  const results = [];
  if (selectNum === 1) {
    return arr.map((value) => [value]);
  }
    
  arr.forEach((value, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, selectNum - 1);
    const attached = combinations.map((combination) => [value, ...combination]);
    results.push(...attached);
  });

  return results;
}

function solution(orders, course) {
    var answer = [];
    
    for (const selectNum of course) {
        
        let map = new Map()
        
        for (let order of orders) {
            if (order.length < selectNum) continue
            
            order = order.split('').sort()
            const cbList = getCombinations(order, selectNum)
            
            for (let cb of cbList) {
                cb = cb.join('')
                map.set(cb, (map.get(cb)||0)+1)
            }
        }
        
        if (map.size===0) continue
        
        map = [...map].sort((a,b)=>b[1]-a[1])
        // console.log(map)
        
        let maxV = map[0][1]
        if (maxV<2) continue 
        
        map.forEach(ele=>{
            if (ele[1]===maxV) answer.push(ele[0])
        })
         
    }
    
    return answer.sort()
}