메뉴 리뉴얼

문제 푸는 키 포인트는 두개다.

 

1. 손님들마다 주문한 단품 메뉴 목록에서 가능한 조합을 목록으로 만든다.

 

손님이 최대 주문 할 수 있는 단품 메뉴의 개수가 10개다. 그러면 10개로 만들 수 있는 조합의 개수는 2^10 - 1개. 알고리즘 시험 문제에서 풀 수 있을 만큼의 범위다. 단품의 개수가 2개 이상인 조합만 고려대상이지만 이건 일단 무시하도록 하자.  코딩으로 조합 목록을 만드는 방법은 다양하게 있을텐데 내 경우에는 비트마스크를 사용했다. 만약 손님이 5개를 주문 했다면 총 31가지 조합이 만들어지므로, 1 ~ 31 까지 For 루프를 돌고 각 회차별로 비트를 확인 해서 단품 목록을 포함 시킬 것인지 말 것인지를 결정한다. 

 

for (int i = 0; i < orders.size(); i++) {

    int totalCombnation = (1 << (orders[i].length())) - 1;
    for (int bit = 1; bit <= totalCombnation; bit++) {
        vector<char> orderSet;
        string combi = "";
    
        for (int position = 0; (1 << position) <= bit; position++) {
            if (bit & (1 << position)) {
                orderSet.push_back((char) orders[i][position]);
            }
        }

        sort(orderSet.begin(), orderSet.end());

        for (int i = 0; i < orderSet.size(); i++) {
            combi += orderSet[i];
        }

 

totalCombination은 현재 주문에서 가능한 조합이 가능한 총 개수다. bit는 1에서부터 totalCombination 까지 순회하면서 단품 목록에서 조합이 가능한 쌍의 집합을 의미한다. 조합에 포함할지 말지는 position 변수가 있는 For 문에서 결정한다. 포함 유무는 orderSet 에 담고 오름차순으로 정리하고 문자열로 조합을 만들었다. 

 

2. 주문 조합 별로 노출 횟수 관리하기

 

모든 주문들의 조합을 순회하면서 노출된 횟수를 저장해야한다. 간단한 방법은 모든 주문 조합 별로 인덱싱이 가능한 int 배열을 만든 다음에 각각을 순회하면서 노출 횟수를 카운트 하는 것이다. 그런데 주문개수가 10개인 경우 알파벳 형태로 가능한 조합의 총 개수는 (26)*(25)*...(17) 이므로 배열에 둘 수 있는 구조가 아니다. 이럴때는 해시 자료구조를 쓴다. 문제에서 주어진 조건으로 가능한 모든 주문의 조합은 10 * 1024개이므로 해시 구조의 최적화를 이용한다면 메모리 범위 내에서 모든 자료구조를 담을 수 있다. 

 

map<string, int> combinations;
map<string, int>::iterator it = combinations.find(combi);

if (it == combinations.end()) {
    combinations.insert(make_pair(combi, 1));
} else {
    it->second++;
}

key와 value가 string, int인 해시 함수를 이용해서 주문 조합의 노출 횟수를 관리했다. 현재 주문 조합이 해시함수에 없으면 새로운 조합을 추가했고 있다면 노출 횟수를 +1 시켜주는 함수다. 이렇게 관리한 자료구조로 노출이 가장 많은 주문 조합을 고를 수 있다.

 

https://github.com/kwony/algorithm/blob/main/Programmers/72411.cpp