프로그래머스: 메뉴 리뉴얼- javascript(재귀 이용한 조합, 객체)

문제 출처 

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

프로그래머스

 

문제 풀이 힌트 

주문 목록과 코스 길이 배열을 기반으로, 각 주문에서 특정 길이의 메뉴 조합을 추출하여 가장 많이 주문된 메뉴 조합을 찾는 문제다. 

1. 주문에서 메뉴 조합 생성: 각 주문을 순회하며, 길이 n의 모든 메뉴 조합을 생성합니다. 이때 조합은 사전 순서로 정렬된 문자열로 변환합니다.
2. 조합의 빈도수 계산: 생성된 메뉴 조합을 Map에 저장하고, 빈도수를 계산합니다. 조합이 이미 존재하면 빈도수를 증가시키고, 존재하지 않으면 새로 추가합니다.
3. 최대 빈도수 찾기: 각 조합의 빈도수 중 최대값을 찾아냅니다. 빈도수가 2 이상인 경우에만 그 조합을 유효한 코스 메뉴로 간주합니다.
4. 최대 빈도수 조합 선택: 최대 빈도수와 같은 조합을 결과 배열에 추가합니다.
5. 결과 정렬 및 반환: 결과 배열을 알파벳 순서로 정렬하여 반환합니다.
6. 재귀를 통한 조합 생성: 조합을 생성하는 함수 getCombinations는 재귀적으로 호출되어, 주어진 길이의 모든 조합을 반환합니다.

 

문제 풀이 코드 

function solution(orders, course) {
    let answer = []; // 결과를 저장할 배열 초기화
    let map = new Map(); // 메뉴 조합의 빈도수를 저장할 Map 객체 초기화

    // 각 코스의 길이(n)에 대해
    course.forEach(n => {
        // 모든 주문을 순회하며
        orders.forEach((order) => {
            // 주문에서 길이 n의 조합을 구함
            const combinations = getCombinations([...order], n);

            // 조합을 순회하며
            combinations.forEach((combi) => {
                // 조합을 정렬하여 문자열로 변환
                combi = combi.sort().join('');
                
                // 해당 조합이 Map에 없으면 추가하고, 있으면 빈도수를 증가시킴
                if (!map.has(combi)) {
                    map.set(combi, 1);
                } else {
                    map.set(combi, map.get(combi) + 1);
                }
            });
        });

        let max = 0; // 가장 많이 주문된 조합의 빈도수를 저장할 변수 초기화

        // Map에 저장된 모든 값(빈도수)을 순회하며
        for (let num of map.values()) {
            // 최대 빈도수를 계산
            max = Math.max(max, num);
        }

        // 최대 빈도수가 2 이상인 경우에만
        if (max >= 2) {
            // Map을 순회하며 최대 빈도수와 같은 조합을 answer에 추가
            for (let [key, value] of map.entries()) {
                if (value === max) answer.push(key);
            }
        }

        // Map을 초기화하여 다음 코스 길이에 대한 조합을 저장할 준비
        map.clear();
    });

    // 결과 배열을 정렬하여 반환
    return answer.sort();
}

// 배열에서 주어진 길이(selectNum)의 모든 조합을 구하는 함수
const getCombinations = (arr, selectNum) => {
    const results = []; // 결과를 저장할 배열 초기화

    // 조합의 길이가 1인 경우, 각 요소를 배열에 담아 반환
    if (selectNum === 1) {
        return arr.map((v) => [v]);
    }

    // 배열의 각 요소를 고정하고, 고정된 요소 이후의 요소로 재귀적으로 조합을 구함
    arr.forEach((fixed, idx, origin) => {
        const rest = origin.slice(idx + 1); // 고정된 요소 이후의 요소를 잘라냄
        const combinations = getCombinations(rest, selectNum - 1); // 재귀적으로 조합을 구함
        const attached = combinations.map((el) => [fixed, ...el]); // 고정된 요소를 앞에 붙임

        // 결과 배열에 모든 조합을 추가
        results.push(...attached);
    });

    return results; // 결과 반환
};

 

Only 문제 풀이 코드 

function solution(orders, course) {
    let answer = []; 
    let map = new Map(); 
    course.forEach(n => {
        orders.forEach((order) => {
            const combinations = getCombinations([...order], n); 
            combinations.forEach((combi) => {
              combi = combi.sort().join('')
                if(!map.has(combi)){
                    map.set(combi,1); 
                }else{
                    map.set(combi,map.get(combi)+1); 
                }
            })
        })
        let max = 0;
        for(let num of map.values()){
           max = Math.max(max, num)
        }
        if(max >=2){
            for(let [key, value] of map.entries()){
                if(value === max) answer.push(key); 
            }
        }
        map.clear()
    })
    return answer.sort(); 
}

const getCombinations = (arr, selectNum) => {
    const results = []; 
    
    if(selectNum ===1){
       return arr.map((v)=>[v])
    }
    
    arr.forEach((fixed, idx, origin) => {
        const rest = origin.slice(idx+1); 
        const combinations = getCombinations(rest, selectNum-1); 
        const attached = combinations.map((el) => [fixed, ...el]) 
    
        results.push(...attached); 
        })
    return results; 
}

 

알고가는 ppoint

01. dfs 이용한 숫자 조합 풀이

		function solution(n, m){         
                let answer=[];
                let tmp=Array.from({length:m}, ()=>0);;
                function DFS(L, s){
                    if(L===m){
                        answer.push(tmp.slice()); 
                    }
                    else{
                        for(let i=s; i<=n; i++){
                            tmp[L]=i;
                            DFS(L+1, i+1);
                        }
                    }
                }
               DFS(0, 1); 
                return answer;
            }
     console.log(solution(4, 2));