[프로그래머스] 72411. 메뉴 리뉴얼

문제 링크

[프로그래머스] 72411. 메뉴 리뉴얼

풀이 과정

const candidateMap = new Map();
const maxCountMap = new Map();
const courseSet = new Set(course);

두 개의 Map 과 한 개의 Set을 사용합니다.

• candidateMap : 주문으로부터 가능한 모든 음식 조합을 등장 횟수와 함께 저장.
• maxCountMap : 배열 course 의 길이 만큼의 음식 조합의 최대 등장 횟수를 저장.
• courseSet : 배열 course 를 Set 으로 만듬. 음식 조합이 만들어졌을 때, has 메소드 를 통해 만들어진 조합의 길이와 일치하는 코스 길이가 존재하는 지 확인하기 위함.

function comb(idx, order, result) {
    if (courseSet.has(result.length)) {
        let count = candidateMap.get(result) || 0;
        candidateMap.set(result, ++count);

        const max = maxCountMap.get(result.length) || 0;

        if (max < count) {
            maxCountMap.set(result.length, count);
        }
    }

    for (let i = idx; i < order.length; i++) {
        comb(i + 1, order, result + order[i]);
    }
}

comb 메소드 는 음식 조합이 만들어 질 때마다, 문제에서 요구하는 코스 요리를 구성하는 단품 갯수에 부합하는 지 확인합니다. 부합한다면, candidate 에는 해당 조합의 등장 갯수를 조정시켜주고, maxCountMap 에는 그 요리 길이의 최대 등장 횟수를 갱신해줍니다.

예를 들면, 두 개의 단품 요소로 구성된 “AB”, “BC”, “CD” 라는 후보 조합들이 사람들에 의해 1번 씩 등장하여 candidate 에 들어 있다고 가정해봅시다. 다음 주문을 통해 “AB” 조합이 다시 한 번 등장했고, 이 메뉴는 결과적으로 총 2 번 등장하게 됩니다. 그럼, 기존 길이 2짜리의 메뉴 조합들은 각각 1번 씩만 등장해서 길이 2에 대한 최대 개수는 1이었지만, “AB” 를 만나게 되면서 “AB”는 두 번 등장하게 되므로 2를 key 로 갖는 객체의 value는 2가 됩니다.

orders.map((order) => order.split("").sort().join("")).forEach((order) => comb(0, order, ""));

위에서 음식 음식 조합을 만드는 comb 메소드를 구현했다면, 이제 comb 메소드를 호출해줍니다. comb 메소드 호출로 candidateMap 와 maxCountMap 을 채웁니다.

1. 먼저, 배열 orders 의 각 요소를 알파벳 오름차순으로 정렬하여 새로운 배열로 구성합니다.
   1. 각 요소에 order 에 대해 split(“”) 을 호출해 문자열을 문자 단위로 잘라 각각을 요소로 하는 배열로 만듭니다.
   2. 1로 만들어진 배열을 sort() 를 호출해 알파벳 오름차순으로 정렬합니다.
   3. 2로 정렬된 배열을 join(“”) 호출을 통해 문자열로 변환합니다.
   4. 각 문자열을 리턴해, 새로 만들어진 문자열을 요소로 갖는 새로운 배열 만들기를 완료합니다.
2. 그 다음에, forEach 메소드로 배열의 각 요소 order 를 파라미터로 전달하여 comb 메소드를 호출합니다.

return course
    .map((length) => {
        const max = maxCountMap.get(length);
        return Array.from(candidateMap)
            .filter((e) => e[0].length === length && e[1] >= 2 && e[1] === max)
            .map((e) => e[0]);
    })
    .flatMap((e) => e)
    .sort();

comb 메소드를 호출해서 candidateMap 와 maxCountMap 을 채웠다면, 이제 각 코스 길이에 맞는 후보를 뽑아 조건에 맞게 변형하여 리턴해줍니다. 아래 과정을 거쳐 정답에 해당하는 배열이 리턴됩니다.

1. 배열 course 를 순회하며(map 메소드 이용), 그 길이 length 에 해당하는 최대 빈도 수를 가져옵니다.
2. candidateMap 을 배열화(Array.from 메소드 이용) 하여 배열로 만듭니다.
3. 만들어진 배열로 filter 메소드를 호출해 조건에 일치하는 요소들만으로 새로운 배열을 만듭니다.
4. filter 를 거친 배열로 map 메소드를 호출해 단품메뉴 조합만을 뽑아 새로운 배열을 만듭니다.
5. 이 배열에 flatMap 메소드를 적용해 배열의 depth 를 한 꺼풀 벗깁니다.
6. sort 메소드를 통해 사전순 오름차순으로 정렬합니다.

코드

function solution(orders, course) {
    const candidateMap = new Map();
    const maxCountMap = new Map();
    const courseSet = new Set(course);

    function comb(idx, order, result) {
        if (courseSet.has(result.length)) {
            let count = candidateMap.get(result) || 0;
            candidateMap.set(result, ++count);

            const max = maxCountMap.get(result.length) || 0;

            if (max < count) {
                maxCountMap.set(result.length, count);
            }
        }

        for (let i = idx; i < order.length; i++) {
            comb(i + 1, order, result + order[i]);
        }
    }

    orders.map((order) => order.split("").sort().join("")).forEach((order) => comb(0, order, ""));

    return course
        .map((length) => {
            const max = maxCountMap.get(length);
            return Array.from(candidateMap)
                .filter((e) => e[0].length === length && e[1] >= 2 && e[1] === max)
                .map((e) => e[0]);
        })
        .flatMap((e) => e)
        .sort();
}

console.log(solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2, 3, 4]));
// console.log(solution(["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2, 3, 5]));
// console.log(solution(["XYZ", "XWY", "WXA"], [2, 3, 4]));