2021 Kakao blind 72411 - 메뉴 리뉴얼(브루트포스, 해쉬) c++, java 풀이

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

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

- 모든 주문 내역을 읽으면서 가능한 요리조합들을 해쉬맵에 저장하면서 1씩 카운트하고, 가능한 조합의 최대 길이를 업데이트해줍니다.

- 그다음에 코스요리 길이 벡터를 읽으면서 해당되는 길이인 음식조합를 ans 벡터에 넣어줍니다. 

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

unordered_map<string, int> foodCnt[11];  // 2~10길이의 코스요리
int maxCnt[11] = {0};

void getComb(string& order, int idx, string result) {  // 고려할 idx, 요리조합
    if (idx == order.length()) {
        int foodlen = result.length();
        if (foodlen >= 2) {
            ++foodCnt[foodlen][result];
            maxCnt[foodlen] = max(maxCnt[foodlen], foodCnt[foodlen][result]);
        }
        return;
    }

    getComb(order, idx + 1, result);               // order[idx] 주문
    getComb(order, idx + 1, result + order[idx]);  // order[idx] 주문 안함
}

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

    for (string& order : orders) {
        sort(order.begin(), order.end());
        getComb(order, 0, "");
    }

    for (int n : course) {
        for (auto& p : foodCnt[n]) {
            if (p.second >= 2 && p.second == maxCnt[n]) {
                ans.push_back(p.first);
            }
        }
    }

    sort(ans.begin(), ans.end());
    return ans;
}

import java.util.*;
import java.util.Map.*;

class Solution {
    Map<String, Integer>[] cnt = new HashMap[11];
    boolean[] check;

    public List<String> solution(String[] orders, int[] course) {
        List<String> ans = new ArrayList<>();

        for (int i = 2; i <= 10; ++i) {
            cnt[i] = new HashMap<String, Integer>();
        }

        for (String order : orders) {
            char[] tmp = order.toCharArray();
            Arrays.sort(tmp);
            order = String.valueOf(tmp);
            check = new boolean[10];
            go(0, "", order);
        }

        for (int n : course) {
            if (cnt[n].isEmpty())
                continue;

            List<Entry<String, Integer>> eList = new ArrayList<Entry<String, Integer>>(cnt[n].entrySet());
            Collections.sort(eList, (a, b) -> b.getValue() - a.getValue());

            int max = eList.get(0).getValue();
            if (max < 2)
                continue;
            for (var e : eList) {
                if (e.getValue() == max)
                    ans.add(e.getKey());
                else
                    break;
            }
        }

        Collections.sort(ans);
        return ans;
    }

    void go(int idx, String pick, String order) {
        if (idx == order.length())
            return;

        int N = pick.length();
        if (N >= 2)
            cnt[N].put(pick, cnt[N].getOrDefault(pick, 0) + 1);

        for (int i = idx; i < order.length(); ++i) {
            if (check[i])
                continue;
            check[i] = true;
            go(i, pick + order.charAt(i), order);
            check[i] = false;
        }
    }
}