문제

https://programmers.co.kr/learn/courses/30/lessons/72411

문제와 제한 사항이 조금 복잡해서 직접 읽는 것이 더 편할 것이다

접근

이번 문제 역시 직접 값들을 하나하나 찾아야 한다.

문제 해결을 2파트로 나눌 수 있다.
1. orders 배열에 있는 각 주문들이 만들 수 있는 조합을 저장하고, 총 몇번이 나오는지 기록하는 부분.
2. course 배열을 만족하는 주문 조합을 출력하는 부분.

조합을 찾기 위해 STL의 next_permutation을 사용하지 않은 이유

저번에 올린 소수 찾기 문제에서는 algorithm 라이브러리에 있는 next_permutation과 substr() 메소드를 이용해서 간단하게 조합을 찾고 set에 저장했다.

하지만 이번엔 주문의 조합 뿐 아니라 조합이 등장한 횟수까지 정확히 count해야하기에 이 방법은 불가능하다

string a = "ABCDE";
do {
	for(int i = 1; i < a.length(); i++) {
    	a.substr(0,i);
    }
    cout << a << endl;
} while (next_permutation(a.begin(),a.end()));

위의 예시처럼 next_permutation을 사용하면 ABCDE에서 나올 수 있는 모든 조합을 출력할 순 있겠지만 중복되어 등장하는 수가 생긴다
(e.g. "ABCDE"에서 "ABC"를 가져오고 "ABCED"에서 "ABC"를 또 가져오기)

따라서 unordered_map과 DFS를 사용해서 각 조합을 한번만 등장시키기 위한 코드를 짤 것이다.

코드 구현

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;
unordered_map<string, int> combination[11];
int maxMenu[11] = {0,};

void dfs(string order, string partial, int index) {
    if(index >= order.length()) 
        return;

    dfs(order, partial, index+1);

    partial += order[index];
    combination[partial.length()][partial]++;

    if (combination[partial.length()][partial] > maxMenu[partial.length()]) {
        maxMenu[partial.length()] = combination[partial.length()][partial];
    }

    dfs(order, partial, index+1);
}


vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;

    // 각 주문마다 dfs를 한번씩 돌리면서 조합과 횟수를 찾아낸다.
    for(string order : orders) {
        sort(order.begin(), order.end());
        //정렬된 주문의 첫번째 메뉴로 init한다.
        
        dfs(order, "", 0);
    }

    for (int num : course) {
        for(auto comb : combination[num]) {
            if (maxMenu[num] >= 2 && comb.second == maxMenu[num]) {
                answer.push_back(comb.first);
            }   
        }
    }
    
    sort(answer.begin(), answer.end());

    return answer;
}

사용한 Data structure

• unordered_map<string, int> combination[MAX_MENU]
  map의 key에는 메뉴조합, value에는 등장한 횟수를 저장한다 (e.g. {"ABC", 3} => 메뉴 A, B, C가 주문 목록에 3번 등장했다)
  메뉴조합의 길이 (i.e. 조합된 주문의 요리 갯수) 에 따라 다른 배열에 저장한다 (e.g. "AB"는 길이가 2니 combination[2]에 저장. "BDE"는 combination[3]에 저장)

• int maxMenu[MAX_MENU]
  각 메뉴조합의 길이가 최대로 등장한 횟수를 저장하는 배열

• 문제에서 각 사람의 주문량은 최대 10개라고 했으니 MAX_MENU에 11을 넣었다.

References

https://www.youtube.com/watch?v=22tBC3YXVPA&list=PL6YHvWRMtz7DhuPHdUZ0WLB5fNO729mbm&index=2&ab_channel=ezsw
https://holicaz.tistory.com/5

만약 더 나은 풀이나 잘못된 로직이 있다면 댓글을 통해 알려주시면 감사하겠습니다 :)