[DFS, Bit-Operation, Set] (프로그래머스 Lv 2) 메뉴 리뉴얼

문제

• 문제 링크
• 문제 설명: 각 손님이 이전에 주문한 메뉴 조합들(orders)과 앞으로 만들 메뉴 조합들 각각의 단품 메뉴 개수 목록(course)이 주어질 때, 이전에 2번 이상 주문된 단품 메뉴들 중 원하는 개수만큼 메뉴를 조합할 때 각 코스별 가장 많이 주문된 것들을 반환하는 함수를 작성하기
• 입력
  • orders 배열의 크기는 2 이상 20 이하
  • orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열
  • 각 문자열은 알파벳 대문자로만 구성
  • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않음
  • course 배열의 크기는 1 이상 10 이하
  • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬
  • course 배열에는 같은 값이 중복해서 들어있지 않음
• 출력
  • 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 반환
  • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 함
  • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담을 것

orders	course	result
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]	[2,3,4]	["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]	[2,3,5]	["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]

풀이

• 먼저 단품 메뉴마다 몇 명이 주문했는지 알기 위해 단품 메뉴별 주문한 사람 수(freq)를 구함
• course 목록에 있는 개수대로 메뉴를 조합. (조합을 구현할 때는 항상 DFS)
  • dfs(pos, comb, ...) 에서 pos가 필요한 이유: 메뉴 A -> 메뉴 B 와 메뉴 B -> 메뉴 A 는 동일하며 중복을 없애기 위해 다음 호출 시 pos 를 1씩 증가시켜준다. 게다가 오름차순 정렬도 자연스레 된다.
• 메뉴를 조합한 후 결과가 여러 개일 때 가장 많이 주문한 것들을 구해야 함.
  • orders의 원소는 알파벳 대문자만 포함하기 때문에 단품 메뉴는 최대 26개
  • orders 배열의 크기는 최대 20이므로 각 메뉴를 주문한 최대 사람 수도 20이 된다.
  • 32보다 작은 숫자이므로 32비트 정수형 변수에 비트로 저장하면 AND 연산으로 메뉴 A와 메뉴 B를 주문한 사람을 쉽게 알아낼 수 있게 된다.
    • freq[i] 는 i번 메뉴 (=메뉴 i + 'A')를 주문한 사람의 인덱스번째 비트를 1로 가짐
    • orders를 순회할 때마다 OR 연산으로 해당 단품 메뉴를 주문한 사람 목록을 쉽게 구할 수 있다.
    • __builtin_popcount() 를 활용하여 1-bit의 개수를 얻으면 주문한 사람 수도 쉽게 얻을 수 있다.
  • course 배열마다 dfs를 호출할 필요 없이 dfs를 1번 호출해서 단품 메뉴의 조합 개수를 늘릴 때마다 course에 있는 개수인지 검사해서 있으면 해당 메뉴 조합을 주문한 사람 수를 저장
    • 메뉴 A와 메뉴 B를 주문한 사람의 목록은 freq[0] & freq[1] 을 해서 구하면 된다. dfs 를 재귀호출할 때마다 인자로 넘기기
  • 메뉴 조합의 개수별로 dfs로 구한 전체 메뉴 조합을 나눈다. set 을 쓰면 삽입하면서 주문한 사람수 오름차순으로 자동 정렬할 수 있다.
  •  각 조합 개수마다 가장 많이 주문한 것들을 answer 배열에 저장한다.
• 정답 코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

void dfs(int pos, string comb, int found, vector<int>& freq,
         vector<int>& course, vector<pair<int, string>>& ret)
{
    // course 에 있는 메뉴 조합의 개수이면
    if (binary_search(course.begin(), course.end(), (int)comb.size())) {
        // 해당 조합에 포함된 단품메뉴를 주문한 사람 수 계산
        int num_found = __builtin_popcount(found);
        // set에 오름차순을 위해 -1을 곱함
        if (num_found > 1) ret.emplace_back(-num_found, comb);
    }
    
    for (int i = pos; i < 26; i++)
        if (__builtin_popcount(freq[i]) > 1) // 단품 메뉴 주문 수 > 1 일 때만 포함
            dfs(i+1, comb + char(i+'A'), found & freq[i], freq, course, ret);
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    // 주문한 사람 목록 구하기
    vector<int> freq(26, 0);
    for (int i = 0; i < orders.size(); i++)
        for (int j = 0; j < orders[i].size(); j++)
            freq[orders[i][j]-'A'] |= (1 << i);
    
    // 모든 가능한 메뉴 조합 구하기
    vector<pair<int, string>> ret;
    dfs(0, "", (1<<21)-1, freq, course, ret);
    
    // 조합 메뉴 개수별로 조합 목록 나누기
    set<pair<int,string>> combinations[11];
    for (int i = 0; i < ret.size(); i++)
        combinations[ret[i].second.length()].insert(ret[i]);
    
    // 개수마다 최대 주문량을 가진 메뉴 조합 저장
    for (int i = 2; i < 11; i++) {
        if (combinations[i].size() == 0) continue;
        auto it = combinations[i].begin();
        int max_orders = it->first;
        while (it != combinations[i].end() and it->first == max_orders) {
            answer.push_back(it->second);
            it++;
        }
    }
    
    // 정렬해서 반환
    sort(answer.begin(), answer.end());
    return answer;
}