[프로그래머스 2021 KAKAO BLIND RECRUITMENT] 메뉴 리뉴얼

문제

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

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

 

풀이

1. 우선 각각의 손님이 주문한 음식들로부터 음식들을 조합하여 원하는 길이(course[])만큼의 메뉴구성을 해주고, map의 key엔 메뉴구성을 value엔 그 개수를 담아 메뉴구성을 카운트합니다.

 

2. map을 순회하며 그 값(가능한 조합의 개수)가 2이상인 것들만 선택하여 길이를 인덱스로 갖는 벡터(cand)에 메뉴구성을 넣어줍니다.

 

3. 마지막으로 course를 순회하며 cand벡터에서 가장 길이가 긴 것들만 정답에 넣어주면 됩니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, string> pis;
string target;
map<string, int> mp;
vector<pis> cand[11];
bool chk[11];
 
void comb(int idx, int cnt, string combmenu) {
	if (idx == target.size()) return;
	if (cnt == 0) {
		sort(combmenu.begin(), combmenu.end());
		mp[combmenu]++;
		return;
	}
	for (int nxt = idx; nxt < target.size(); nxt++) {
		if (!chk[nxt]) {
			chk[nxt] = 1;
			comb(nxt, cnt - 1, combmenu + target[nxt]);
			chk[nxt] = 0;
		}
	}
}
 
bool cmp(pis i, pis j) {
	if (i.first == j.first) return i.second < j.second;
	return i.first > j.first;
}
 
vector<string> solution(vector<string> orders, vector<int> course) {
	vector<string> answer;
	// #1 주문들에서 조합 생성해보기
	for (string menu : orders) {
		for (int num : course) {
			memset(chk, 0, sizeof(chk));
			target = menu;
			comb(0, num, "");
		}
	}
	// #2 단품메뉴 조합 후보에 넣기
	for (auto i : mp) {
		if (i.second < 2) continue;
		cand[i.first.size()].emplace_back(i.second, i.first);
	}
	for (int i : course) {
		sort(cand[i].begin(), cand[i].end(), cmp); // 크기 순으로 정렬 후, 첫 원소의 주문횟수(최대)와 같은것만 정답
		int len = cand[i][0].first;
		for (pis j : cand[i]) {
			if (j.first == len) answer.emplace_back(j.second);
		}
	}
	sort(answer.begin(), answer.end());
	return answer;
}