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

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

2021/04/23

문제 접근 방법

course의 요소(숫자)마다 모든 문자열을 반복하며
요소(숫자)개를 선택하는 조합을 생성한다.
가장 많이 나온 조합을 기록하고 (동률일 경우 모두)
2번 이상 나오지 않은 조합은 제외시킨다.

helper함수

문자열에서 num개 선택하는 조합을 Array로 돌려주도록 한다.

조합선택은 디자인하기 수월하도록 recursion을 도입.

완성한 solution

function solution(orders, course) {
    let answer = [];
    // amount = 선택할 개수
    for (let amount of course) {
        let temp = {};
        for (let i = 0; i < orders.length; i++) {
            for (let j of helper(orders[i], amount)) {
                temp[j] = temp[j] ? temp[j] + 1 : 1 // 각 조합이 몇번 등장했는지 기록
            }
        }
        // 현재 amount에서 기록된 모든 조합을 등장횟수의 내림차순으로 정렬.
        temp = Object.entries(temp).sort((a, b) => - a[1] + b[1]);
        // [[조합, 등장횟수], [조합, 등장횟수], ...] 의 형태를 [조합, 조합, 조합] 으로 변경하고
        // 가장 많이 등장한 (동률일 경우 모두) 조합을 answer에 담는다.(단 2번 이상 등장했어야 한다.)
        answer.push(...temp.filter((val) => (val[1] === temp[0][1]) && (val[1] > 1)).map((val) => val[0]))
    }
    return answer.sort();
}
// 문자열을 num개 선택하는 조합을 돌려주는 함수 (recursion)
function helper(word, num) {
    let temp = [];
    if (num === 1) return [...word];
    else if (word.length < num) return [];
    for (let i = 0; i < word.length; i++) {
        temp.push(...helper(word.slice(i + 1), num - 1).map((val) => word[i] + val));
    }

    return temp.map((val) => [...val].sort().join(''));
}

num개 선택하는 모든 조합 구하는 방법

문자열을 0번째 index부터 문자열의 길이까지 순회하며
0번째부터 현재 index까지를 제외한 문자열에 대해 현재 함수를 재귀호출한다.
그 결과의 모든 요소에 현재 index에 해당하는 char(문자)를 삽입한다.

간혹 문자열 순서에 의해 'XY'와 'YX'처럼 다른 조합으로 인식될 수 있기에
Array내의 모든 요소를 오름차순으로 정렬하였다.

아쉬웠던점

자주 반복되고 의미없는 과정이 존재했다.
helper함수는 재귀호출되는데 조합을 기록하는곳은 최초 호출하는곳에서만 이뤄지기 때문에
해당 함수 내부에서 요소들의 문자열을 정렬할 필요가 없었다.
오히려 각 재귀호출마다 정렬하기에 무의미한 시간을 잡아먹고 있었다.

또, filter와 map을 사용하며 2번의 반복을 진행하기보다
reduce를 사용하여 한차례의 반복에 결과를 도출하도록 하는게 좋겠다는 생각이 들었다.

바뀐 solution

function solution(orders, course) {
    let answer = [];
    // amount = 선택할 개수
    for (let amount of course) {
        let temp = {};
        for (let i = 0; i < orders.length; i++) {
            // 모든 요소들을 문자열의 오름차순으로 정렬하여 한다.
            // ex) ['CBA', 'DSF'] => ['ABC', 'DFS']
            for (let j of helper(orders[i], amount).map((val) => [...val].sort().join(''))) {
                temp[j] = temp[j] ? temp[j] + 1 : 1 // 각 조합이 몇번 등장했는지 기록
            }
        }
        // 현재 amount에서 기록된 모든 조합을 등장횟수의 내림차순으로 정렬.
        temp = Object.entries(temp).sort((a, b) => - a[1] + b[1]);
        // [[조합, 등장횟수], [조합, 등장횟수], ...] 의 형태를 [조합, 조합, 조합] 으로 변경하고
        // 가장 많이 등장한 (동률일 경우 모두) 조합을 answer에 담는다.(단 2번 이상 등장했어야 한다.)
        answer.push(...temp.reduce((acc, cur, index, ori) => {
            if (cur[1] > 1 && cur[1] === ori[0][1]) acc.push(cur[0]);
            return acc;
        }, []))
    }
    return answer.sort();
}
// 문자열을 num개 선택하는 조합을 돌려주는 함수 (recursion)
function helper(word, num) {
    let temp = [];
    if (num === 1) return [...word];
    else if (word.length < num) return [];
    for (let i = 0; i < word.length; i++) {
        temp.push(...helper(word.slice(i + 1), num - 1).map((val) => word[i] + val));
    }
    return temp;
}