2021 KAKAO Blind - 2. 메뉴 리뉴얼

목차

개요

풀이

코드

 

 

개요

카카오 2021년 블라인드 채용 2번 문제 메뉴 리뉴얼입니다.

위와 같은 표가 있을 때, 가장 가능성이 높은 세트 메뉴들을 정하는 건데요. 가령, 2개의 메뉴로 이루어진 세트 메뉴를 구성하고 싶을 때, {A, C} 세트는 1번, 2번, 4번, 6번 손님이 주문한 이력이 있으므로 세트 메뉴 구성하기에 좋습니다.

뿐만 아니라, 3개, 4개의 메뉴로 이루어진 세트 메뉴도 다음과 같이 정리해 볼 수 있습니다.

 

이처럼, 손님들의 주문 이력과 코스 내 메뉴 개수를 입력으로 받아 가장 좋은 세트 메뉴를 구성하여 리턴 하는 것이 이 문제입니다.

 

 

풀이

이 문제는 수의 범위가 크지 않고 효율성을 체크하지 않습니다. 최대 20명의 손님이 이력을 남겨주셨고, 한 손님 당 남긴 주문 이력은 10가지 이내, 세트 메뉴 조합 구성은 10개 이내입니다. 따라서 DFS와 같은 방법으로 임의의 조합이 얼만큼 나왔는지 전부 구해볼 수 있겠지요. (Brute force, Back tracking, Combination)

 

Step 1: Preprocessing

데이터가 가장 많을 때 처리해야 하는 경우의 수는 다음과 같을 것입니다.

$$20 \sum{_{k=2} ^{10}\ {_{10}C_{k}}}$$

 

가장 먼저, DFS를 호출하기 전에 전 처리 과정입니다. 손님의 주문 이력이 정렬되어 있다는 보장이 없으므로 sort(s.begin(), s.end()) 를 통해서 오름차순 정렬을 해줍니다.

이후 dfs를 돌면서 세트 구성 메뉴가 2개일 때, 3개일 때, ... , s 전체를 모두 세트로 구성할 때 까지 확인해줍니다.

for(auto itr = orders.begin(); itr != orders.end(); itr++){
    string s = *itr;
    int s_len = s.length();
    sort(s.begin(), s.end());
    for(int i=2; i<=s_len; i++){
        dfs(0,s, "", i);
    }
}

 

Step 2: DFS

아래는 DFS 함수입니다. 보통 DFS는 재귀 함수로 구현을 하죠.

s는 손님 1명의 주문 이력입니다. t는 dfs를 재귀적으로 호출해가면서 정보(가능한 세트 메뉴 조합)를 누적하기 위한 변수입니다. target_len은 몇 개의 메뉴를 1개의 세트로 구성하고 싶은 지에 대한 값입니다.

void dfs(int index, string s, string t, int target_len)

 

index는 현재까지 참고한 손님의 주문 이력 내 index 번호입니다. 조합을 구성할 때, 순서는 중요하지 않습니다. 따라서, dfs를 돌면서 가능한 세트 메뉴로서 조합에 넣을지 안 넣을지 한 번이라도 체크해본 메뉴는 다시 고려할 필요가 없습니다. 따라서 i+1을 누적 해가며 시간을 절약해줍니다.

 

또한, dfs를 호출할 때 t에 s[i] 메뉴를 함께 저장해서 호출해주도록 합니다.

for(int i=index; i < s_len; i++){
    dfs(i+1, s, t+s[i], target_len);
}

 

마지막으로 재귀 함수 종결 조건입니다. dfs를 호출하면서 계속 정보를 누적 하다가 이 길이가 target_len과 같아질 때 dfs를 종료하면 됩니다. 이 시점에는 t에 한 가지 가능성이 있는 세트 메뉴 조합이 나올텐데, 이를 map 자료구조에 1 증가 시켜줍니다.

 

같은 자료구조를 다른 손님의 이력에 대해서도 사용 할테니, 모든 손님에 대해서 dfs를 수행하고 나면 map 자료구조에 세트 메뉴 조합과 손님 개수가 pair로 나올 것입니다.

map<string, int> m[9];
void dfs(int index, string s, string t, int target_len){
    if(t.length() == target_len){
        m[target_len-2][t]+=1;   
        return;
    }
    [...]
}

 

만약 이 과정을 모든 손님들에 대해서 수행하고 나면, map 자료구조에는 다음과 같은 값이 들어가게 됩니다.

Combination: AB, #people: 1
Combination: AC, #people: 4
Combination: AD, #people: 2
[...]
Combination: ABC, #people: 1
Combination: ABF, #people: 1
[...]
Combination: CDE, #people: 3
Combination: CDH, #people: 1
[...]
Combination: ABFG, #people: 1
Combination: ACDE, #people: 2
[...]
Combination: ADEH, #people: 1
Combination: BCFG, #people: 2
Combination: CDEH, #people: 1
[...]

 

Step 3: 최대값 찾기

이제 구성하고자 하는 세트 메뉴의 개수에 맞추어 다시 정리해주면 됩니다. 즉, 세트 메뉴 수가 2인 경우, m[0]을 순회하면서 손님 수의 최대 값을 구한 뒤, 그 최대 값과 같은 메뉴들을 모두 answer vector에 넣어주면 됩니다.

이 과정을 course 내에 있는 모든 메뉴 수에 대해서 처리해주면 됩니다.

마지막으로, answer vector는 course 순서([2,3,4])가 아닌 단순 오름차순이므로 다시 정렬해주면 됩니다.

for(auto itr = course.begin(); itr != course.end(); itr++){
    int max = 0;
    for(auto pair = m[*itr-2].begin(); pair != m[*itr-2].end(); pair++){
        if(max < pair->second) max = pair->second;
    }
    if(max <=1) continue;
    for(auto pair = m[*itr-2].begin(); pair != m[*itr-2].end(); pair++){
        if(pair->second == max) answer.push_back(pair->first);
    }
}

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

 

코드

제 코드가 최적의 코드는 아니지만, 참고용으로 올렸습니다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
map<string, int> m[9];
void dfs(int index, string s, string t, int target_len){
    if(t.length() == target_len){
        m[target_len-2][t]+=1;   
        return;
    }
    int s_len = s.length();
    for(int i=index; i < s_len; i++){
        dfs(i+1, s, t+s[i], target_len);
    }
}
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(auto itr = orders.begin(); itr != orders.end(); itr++){
        string s = *itr;
        int s_len = s.length();
        sort(s.begin(), s.end());
        for(int i=2; i<=s_len; i++){
            dfs(0,s, "", i);
        }
    }

    for(auto itr = course.begin(); itr != course.end(); itr++){
        int max = 0;
        for(auto pair = m[*itr-2].begin(); pair != m[*itr-2].end(); pair++){
            if(max < pair->second) max = pair->second;
        }
        if(max <=1) continue;
        for(auto pair = m[*itr-2].begin(); pair != m[*itr-2].end(); pair++){
            if(pair->second == max) answer.push_back(pair->first);
        }
    }

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

    return answer;
}