[프로그래머스] - "메뉴 리뉴얼" C++ / 조합 / map

문제 링크

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

프로그래머스

 

풀이과정

# 해석

파라미터로 orders (모든 주문) , course (코스를 구성하는 요리의 개수) 두가지가 주어지며,

orders에 담긴 단품메뉴들을 course에 적힌 개수만큼 조합해서 코스요리를 만드는 것이 목표입니다.

 

고려해야 할 점은

1. 코스요리로 만들 단품요리들은 2번이상 손님에게 주문된 메뉴여야 합니다.

2. 2번 이상 주문된 메뉴들이라도 전부 코스요리가 될 수 있는것은 아니며,

"코스를 구성하는 요리의 개수 별"로 가장 많이 주문된 메뉴들 만이 코스요리가 될 수 있습니다.

 

예를들어 3가지 요리로 구성된 코스요리 조합을 따져봤을 때

A B C

B D E

C B A

B E D

A B C

D F G

B D E

 

이런 결과가 나왔다면

A B C : 3번

B D E : 3번

D F G : 1번

주문되었으므로 "A B C", "B D E"가 코스요리가 되는 것입니다.

 

예제에서 봤듯이 A B C 와 C B A 는 같은 요리가 되며, 가장 많이 주문된 코스요리가 2개 이상이면 전부 코스요리가

될 수 있습니다.

 

# 풀이

1. 먼저 모든 주문(orders)에 대해 course 에 담긴 개수로 만드는게 가능한 조합의 경우의 수를 구해줘야 합니다.

주문한 단품메뉴의 개수가 course에 적힌 개수보다 크다면 조합을 구해주면 됩니다.

orders[i] C course[j]

* 다만 조건에 의해 A B C 와 C B A는 같은 요리가 되기 때문에 조합을 구하기 전에 먼저 정렬을 해주어야 합니다.

그 후 모든 경우의 수에 대해 map을 활용하여 어떤 코스요리가 몇번 주문되었는 지를 기록합니다.

// 주문으로 만들 수 있는 모든 조합을 찾는다.
for(string order:orders) {
	sort(order.begin(), order.end());
	for(int i=0; i<course.size(); i++) {
		if(course[i] <= order.size()) comb(order,0,0,"",course[i]);
	}
}

(조합 구현방법 바로가기)

 

2. 다음으로 기록한 결과에 대해 두 번 이상 주문된 코스요리만 따로 저장해줍니다.

가장 많이 주문한 코스요리가 무엇인지 알아야 하기 때문에 주문 횟수에 대해 내림차순으로 정렬했습니다.

bool cmp(pair<int,string> a, pair<int,string> b) {
	return a.first > b.first;
}

...


vector < pair <int, string> > sortV;
for(auto item:ordersMap) {
	if(item.second >= 2) sortV.push_back({item.second, item.first});
}
// 주문 횟수로 내림차순 정렬
sort(sortV.begin(),sortV.end(),cmp);

 3. 정렬한 코스요리들은 이제 주문횟수가 가장 많은 순서대로 정렬되어 있기 때문에

차례로 for문을 돌려서 정답을 구할 수 있습니다.

for(int i=0; i<course.size(); i++) {
	int maxCnt = 0;
	for(int j=0; j<sortV.size(); j++) {
		string food = sortV[j].second;
		// 크기가 같은 주문에 대해서만 체크
		if(course[i] != food.size()) continue;
		// 가장 많이 주문한 주문 저장
		if(maxCnt == 0) {
			answer.push_back(sortV[j].second);
			maxCnt = sortV[j].first;
		}
		// 가장 많은 주문횟수가 또 있다면 저장
		else if(maxCnt == sortV[j].first) answer.push_back(sortV[j].second);
		// 그 이후는 고려하지 않음
		else break;
	}
}
sort(answer.begin(),answer.end());

 

전체 코드

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

bool check[10];
map < string, int > ordersMap;

// 조합 
void comb(string s, int idx, int cnt, string result, int size) {
	if(cnt == size) {
		ordersMap[result]++;
		return;
	}
	for(int i=idx; i<s.size(); i++) {
		if(check[i] == 0) {
			check[i] = 1;
			result += s[i];
			comb(s,i+1,cnt+1,result,size);
			result.pop_back();
			check[i] = 0;
		}
	}
}

bool cmp(pair<int,string> a, pair<int,string> b) {
	return a.first > b.first;
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
	// 주문으로 만들 수 있는 모든 조합을 찾는다.
	for(string order:orders) {
		sort(order.begin(), order.end());
		for(int i=0; i<course.size(); i++) {
			if(course[i] <= order.size()) comb(order,0,0,"",course[i]);
		}
	}

	vector < pair <int, string> > sortV;
	for(auto item:ordersMap) {
		if(item.second >= 2) sortV.push_back({item.second, item.first});
	}
	// 주문 횟수로 내림차순 정렬
	sort(sortV.begin(),sortV.end(),cmp);

	for(int i=0; i<course.size(); i++) {
		int maxCnt = 0;
		for(int j=0; j<sortV.size(); j++) {
			string food = sortV[j].second;
			// 크기가 같은 주문에 대해서만 체크
			if(course[i] != food.size()) continue;
			// 가장 많이 주문한 주문 저장
			if(maxCnt == 0) {
				answer.push_back(sortV[j].second);
				maxCnt = sortV[j].first;
			}
			// 가장 많은 주문횟수가 또 있다면 저장
			else if(maxCnt == sortV[j].first) answer.push_back(sortV[j].second);
			// 그 이후는 고려하지 않음
			else break;
		}
	}
	sort(answer.begin(),answer.end());
    return answer;
}