문제 설명 및 링크

프로그래머스 - 메뉴 리뉴얼

나의 풀이

모든 주문으로부터 코스가 가능한 조합을 전부 뽑아서 카운팅하는 문제이다.

• 코스가 가능한 모든 조합을 구함 (재귀)
• 각 조합의 카운팅 후 코스에 추가

뭐 문제는 이렇게 풀면 되긴 하는데... 이게 최대 효율의 알고리즘은 아니다.

다른 사람 코드를 보니 코스가 가능한 모든 조합을 구하는 동시에 카운팅을 하는 방법도 있다.

이게 더 괜찮은 방법으로 보인다. (역시 고수는 많구만)

그나저나 if 문 하나 까먹어서 1시간을 날려먹었네 ㅜㅜ

코드

모든 프로그래머스 문제 관련 코드들은 GitHub 링크 에 있음.

const getTargets = (targetStr, remainStr, count) => {
    if (targetStr.length === count) {
        return [targetStr];
    }
    
    let result = [];
    
    for (let i = 0; i < remainStr.length; i++) {
        const newTargetStr = targetStr + remainStr.slice(i, i + 1);
        const newRemainStr = remainStr.slice(i + 1);
        
        result = result.concat(getTargets(newTargetStr, newRemainStr, count));
    }
    
    return result;
}

const getTargetCount = (target, orders) => {
    const arrTarget = target.split('');
    
    let count = 0;
    
    for (let i = 0; i < orders.length; i++) {
        let isOk = true;
        for (let j = 0; j < arrTarget.length; j++) {
            if (!orders[i].includes(arrTarget[j])) {
                isOk = false;
                break;
            }
        }
        
        if (isOk) {
            count++;
        }
    }
    
    return count;
};

const getAllTargets = (orders, course) => {
    let targets = [];
    
    course.map(c => {
        orders.map(order => {
            if (order.length < c) {
                return;
            }
            
            targets = targets.concat(getTargets('', order, c));
        });
    });
    
    return [...new Set(targets)];
};

function solution(orders, course) {
    var answer = [];
    
    // 데이터 정렬
    orders = orders
        .filter(order => order.length >= course[0])
        .map(order => order.split('').sort().join(''))
        .sort((o1, o2) => o1.length - o2.length);
    
    course = course.filter(c => c <= orders[orders.length - 1].length);
    
    // 코스 가능한 모든 타겟 가져오기
    const targets = getAllTargets(orders, course);
    
    const resultMap = {};
    
    // 각 타겟의 개수 카운팅 후 코스에 넣을 건지 결정
    targets.map(target => {
        if (!resultMap[target.length]) {
            resultMap[target.length] = { list: [], maxCount: 0 };
        }
        
        const targetCount = getTargetCount(target, orders);
        
        if (targetCount < 2) {
            return;
        }
        
        if (targetCount > resultMap[target.length].maxCount) {
            resultMap[target.length] = { list: [target], maxCount: targetCount };
        } else if (targetCount === resultMap[target.length].maxCount) {
            resultMap[target.length].list.push(target);
        }
    });
    
    for (let key in resultMap) {
        answer = answer.concat(resultMap[key].list);
    }

    answer = answer.sort((a1, a2) => a1 > a2 ? 1 : -1);
    
    return answer;
}