[프로그래머스] 메뉴 리뉴얼 (2021 KAKAO Blind Recruitment)

문제 링크

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

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

 

풀이

1) 각 order마다 가능한 모든 메뉴 조합을 구해줍니다. ( line 8 ~ 18 )

2) order 전체에 대해1에서 구한 각 조합이 몇 번씩 나오는지 카운팅해줍니다. ( line 16 )

3) course 개수 별로 가장 많이 나온 조합들을 리스트로 구해줍니다. ( line 20 ~ )

 

정답 코드

Javascript

function solution(orders, course) {
    const setAllCombination = function(cnt, order){
        const n = order.length;
        for(let comb = 1; comb < (1 << n); comb++){
            let res = '';
            for(let i = 0; i < n; i++){
                if(comb & (1<<i)) res += order[i];
            }       
            if(res.length < 2) continue;
            if(cnt[res] === undefined) cnt[res] = 0;
            cnt[res]++;
        }
    }
    const cnt = {};
    orders.map(order => order.split('').sort()).forEach(order => setAllCombination(cnt, order));

    const cntArray = Object.entries(cnt).filter(v => v[1] > 1);
    return course.reduce((ans, c) => {
        const tmp = cntArray.filter(v => v[0].length === c);
        const maxVal = tmp.reduce((ret, v) => Math.max(ret, v[1]), -1)
        return ans.concat(tmp.filter(v => v[1] === maxVal).map(v => v[0]));
    }, []).sort();
}

 

C++

#include <bits/stdc++.h>
#define ft first
#define sd second
using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
	map<string, int> m;
	for(string &order: orders){
		sort(order.begin(), order.end());
		int n = order.size();
		for(int comb=3; comb < (1 << n); comb++){
			string x;
	   		for(int i=0; i<n; i++){
				if(comb & (1<<i)) x += order[i];
			}
			if(x.size() > 1) m[x]++;
		}
	}
	
	vector<string> ans;
   	pair<int, vector<string>> tmp[11];
	for(const auto &now: m){
   		string x = now.first;
		int cnt = now.second;
		if(cnt <= 1) continue;
		int len = x.size();
		if(tmp[len].ft < cnt){
			tmp[len] = {cnt, vector<string>(1, x)};
		} else if(tmp[len].ft == cnt){
			tmp[len].sd.push_back(x);
		}
	}
	for(int c: course){
		for(auto x: tmp[c].sd){
			ans.push_back(x);
		}
	}
	sort(ans.begin(), ans.end());
	
	return ans;
}