[ 카카오 ] 메뉴 리뉴얼

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

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

문제,해설 : 문제를 단지 복붙이 아닌 설명을 하겠습니다.

먼저 각 사람들이 주문한 orders 배열이 주어집니다. 그리고 각 단품 메뉴들의 개수가 담겨진 배열들이 주어집니다. 이게 대체 무슨 말인지를 전 전혀~~~~~~~~~~~~~이해 못했었어요.(핵빡대가리세요?라고 말해도 안억울 합니다)

왜냐면 한글인데도 대체 무슨 말을 하는건지 못알아먹었거든요;;;;

 

천천히 해설을 해보면 먼저 각 사람들은 단품 메뉴들을 주문을 합니다. 그리고 우리는 이 단품메뉴들을 적절히 조합해서 '세트'메뉴를 만들려고 합니다. 이때, 세트메뉴를 만들려고 하는데 세트메뉴를 구성하는 단품메뉴의 '갯수'를 지정해 주는 겁니다.

 

즉,예제를 통해 설명하면 

손님 번호주문한 단품메뉴 조합

1번 손님	A, B, C, F, G
2번 손님	A, C
3번 손님	C, D, E
4번 손님	A, C, D, E
5번 손님	B, C, F, G
6번 손님	A, C, D, E, H

이렇게 주문을 했습니다. 그럼 여기서 우린 세트메뉴를 만들어야죠.

카카오는 여기서 세트메뉴를 구성할 수 있는 단품메뉴들의 개수를 줍니다.

예제에선 2,3,4 이죠. 즉, 단품메뉴 2개로 만들 수 있는 세트메뉴,3개로 만들 수 있는 세트메뉴, 4개로 만들 수 있는 단품메뉴 를 만들어라!!!이 말입니다. 이때 가장 많이 나온 세트메뉴를 선택하면 되는거죠.

요리 2개 코스	A, C	1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스	C, D, E	3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스	B, C, F, G	1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스	A, C, D, E	4번, 6번 손님으로부터 총 2번 주문됐습니다.

이렇게 말이죠. 사실상 그렇게 어려운 문제는 아니었지만 문제를 해설하는 것 자체가 너무 힘들었어요;;;

 

코드로 표현하자면 제일 처음 할일은 각 손님마다 주문한 단품메뉴들 중 조합할 수 있는 경우의 수를 싹다 구해놓습니다. 이때 최소 단품메뉴 2개로는 만들 수 있어야 하는 조건을 빼먹지 말고요.

 

그다음 구해놓은 경우의 수들 중 동일한 케이스가 몇번 나왔는지 횟수를 세어줍니다.

이제 절반은 다 푼거죠.

 

여기서 다시 각 단품메뉴 개수의 조건을 충족시키는 케이스들 중 가장 최대로 나온 횟수를 구해 주어 벡터에 담아줍니다.

 

이 벡터를 가지고 다시 탐색을 해줘 답을 구해주면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;

int Visit[10];
map<string, int> mp;
vector<string> orders;
void f(int depth, int index, int end);

vector<string> solution(vector<string> order, vector<int> course) {
    orders=order;
    for (int i = 0; i < orders.size(); i++) {
		f(0,i,orders[i].size());
	}
	vector<string> ans;
	vector<pair<int, int>> v;
	for (int i = 0; i < course.size(); i++) {
		int cnt = 0;
		string push;
		for (auto u : mp)
			if (u.first.length() == course[i] && u.second>=2) {
				if (cnt < u.second)
					cnt = u.second;
			}
		v.push_back({ course[i],cnt });
	}
	for (int i = 0; i < v.size(); i++) {
		for (auto u : mp) {
			if (u.first.length() == v[i].first && u.second == v[i].second)
				ans.push_back(u.first);
		}
	}
	sort(ans.begin(), ans.end());
    return ans;
}
void f(int depth,int index,int end)
{
	if (depth == end) {
		string str = "";
		for (int i = 0; i < end; i++)
			if (Visit[i])
				str += orders[index][i];
        sort(str.begin(), str.end());
		if(str.length()>=2)
			mp[str] += 1;
		return;
	}

	Visit[depth] = 1;
	f(depth + 1,index,end);

	Visit[depth] = 0;
	f(depth + 1,index,end);
}