[Programmers] 메뉴 리뉴얼

문제

 

[프로그래머스] 2021 KAKAO BLIND RECRUITMENT > 메뉴 리뉴얼

코딩테스트 연습 - 메뉴 리뉴얼

 

 

아이디어

 

이 문제는 손님들이 주문한 단품 메뉴들의 조합을 어떻게 세부적으로 나눠서 몇 번 주문했는지를 확인하는지가 핵심이라고 생각합니다.

 

가장 먼저 생각난 방법은 조합입니다.

 

orders 배열의 각 원소의 길이가 n이라고 했을 때 1부터 n개까지 택하는 모든 조합을 구하는 것을 생각했습니다.

 

조합을 이용해도 문제없이 문제를 풀 수 있다고 생각했지만 1부터 n개까지 모든 조합에 대해 구할 것이면 부분집합을 이용하는 것이 더 편리한 구현이 될 것이라고 생각했습니다.

 

orders 배열들의 각 원소는 크기가 2 이상 10 이하인 문자열이라는 조건이 있었고 부분집합의 시간 복잡도는 O(2^n)이기 때문에 부분집합을 적용하는 데 있어서 문제가 없을 것이라고 판단했습니다.

 

부분집합을 이용하는 것을 기반으로 하여 다음과 같은 알고리즘 로직으로 코드를 구현했습니다.

 

1. 초기 인덱스는 0으로 잡고 orders배열을 탐색

2. 인덱스에 해당하는 원소값을 사용하여 부분집합 구하기

3. 부분집합들 중 길이가 2이상인 부분집합만 suborderMap에 key는 부분집합, value는 부분집합이 나온 개수로 하여 저장

4. 모든 인덱스를 탐색할 때까지 1~3를 반복

5. 부분집합들이 저장된 suborderMap을 탐색

6. suborderMap의 원소값이 course길이에 해당되며 개수가 2 이상인지 확인

7. 해당될 경우 sizeMap에 key는 course길이, value는 suborder중 주문량이 가장 큰 값을 저장, orderMap에 key는 course길이, value는 주문량이 가장 큰 suborder들의 리스트 저장

8. 모든 suborder을 탐색할떄까지 5~7을 반복

9. orderMap에 담긴 suborder들을 한 배열에 담아 알파벳 순으로 오름차순

 

 

구현 코드 (JavaScript)

 

function solution(orders, course) {
    const suborderMap = new Map(); // order가 key일 때 order 개수

    for(let i=0; i<orders.length; i++) {
        let temporder = orders[i];
        const order = [];
        for(let j=0; j<temporder.length; j++) {
            order.push(temporder[j]);
        }

        order.sort(); // order 정렬

        let n = order.length;
        for(let j=0; j<(1<<n); j++) { // 부분집합
            let temp = '';
            for(let k=0; k<n; k++) {
                if((j & (1<<k)) !== 0) {
                    temp = temp + order[k];
                }
            }

            if(temp.length >= 2) { // 길이가 2이상인 부분집합만 map에 저장
                if(suborderMap.has(temp)) {
                    suborderMap.set(temp, suborderMap.get(temp)+1);
                } else {
                    suborderMap.set(temp, 1);
                }
            }
        }
    }

    let sizeMap = new Map(); // course가 key일 때 order 개수
    let orderMap = new Map(); // course가 key일 때 order 리스트

    suborderMap.forEach((val, key) => { // order가 key일 때 order 개수
        for(let i=0; i<course.length; i++) {
            if(course[i] === key.length && val >= 2) { // 길이가 course의 i번째이고 
                if(sizeMap.has(key.length)) {
                    if(val === sizeMap.get(key.length)) {
                        const array = orderMap.get(key.length);
                        array.push(key);
                        orderMap.set(key.length, array);
                    } else if(val > sizeMap.get(key.length)) {
                        const array = [key];
                        orderMap.set(key.length, array);
                        sizeMap.set(key.length, val);
                    }
                } else {
                    const array = [key];
                    orderMap.set(key.length, array);
                    sizeMap.set(key.length, val);
                }

                break;
            }
        }
    });

    let res = [];
    orderMap.forEach((val, key) => {
        val.forEach((getVal) => {
            res.push(getVal);
        })
    })

    res.sort();

    return res;
}

 

 

읽어주셔서 감사합니다.