[C++][프로그래머스] 메뉴 리뉴얼 - 비트마스크 완전탐색

문제

이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 

또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

 

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

풀이

코스요리 메뉴를 구성해야합니다.

코스요리는 2가지 이상의 단품메뉴로 구성되어있으며 코스요리를 구성하는 단품메뉴들의 갯수를 course 배열로 입력받습니다. 

 

course 배열이 [2, 3] 이라면 단품요리 2개로 구성된 코스요리 중 가장 인기있는 메뉴, 단품요리 3개로 구성된 코스요리 중 가장 인기있는 메뉴를 반환하면 됩니다.

※ 가장 인기있는 메뉴가 2개 이상이라면 모두 반환합니다.

 

따라서 저는 course_check 배열을 선언하고 아래와 같이 정의하였습니다.

course_check[i] : 단품메뉴 i개로 구성된 코스요리를 추가할지에 대한 여부

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

	for (int i = 0; i < course.size(); i++) {
		course_check[course[i]] = true;
	}
}

 

그 다음으로는 각 손님이 주문한 단품메뉴 조합 내의 모든 부분 집합을 구합니다.
단 부분집합의 크기가 course 집합 중 하나여야 합니다.

로직을 수행하기 전, 주문한 단품메뉴 조합은 정렬되지 않은 상태로 입력되기 때문에 정렬을 선진행해줍니다.

 

먼저 1번 손님이 주문한 단품메뉴 조합 내의 모든 부분 집합을 구해보도록 하겠습니다.

1번 손님이 주문한 단품메뉴 조합 내 모든 부분집합은 대략 아래와 같은 모습일 것입니다. 

 

A, B, C, F, G AB, AC, AF, AG, BC, BF, BG, CF, CG, FG ABC, ABF, ABG, ACF, ACG, AFG, ABCF, ABCG, …

 

1번 손님이 주문한 단품메뉴 조합 내 모든 부분집합을 구하는 방법으로 비트마스크를 이용했습니다.

모든 부분집합에서 size가 2개 이상이며 size가 course 집합에 속하는지 여부를 통해 코스메뉴 후보를 필터링합니다.

 

코스메뉴 후보가 필터링되면 가장 인기있는 코스메뉴를 구하기 위해 Map을 활용하였습니다.

Map 배열을 다음과 같이 정의하였습니다.

Map[i]<key(코스메뉴), value(주문 횟수)> :  i개의 단품메뉴로 구성된 코스메뉴에 대한 주문횟수를 갖는다.

 

Map[2]

Map[3]

 

"스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 배열 course에 들어있기 때문에

Map[코스요리를 구성하는 단품메뉴의 수]를 주문 횟수 기준으로 내림차순 정렬하여 가장 많은 주문을 받은 구성을 뽑아낼 수 있습니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

bool course_check[11] = { false, };

string sort_string(string order) {
	vector<char> chars;
	for (int j = 0; j < order.size(); j++) {
		chars.push_back(order[j]);
	}
	sort(chars.begin(), chars.end());

	string sorted_string = "";
	for (int j = 0; j < chars.size(); j++) {
		sorted_string += chars[j];
	}

	return sorted_string;
}

int countBit(int n) {
	int count = 0;

	while (n) {
		if (n & 1) count++;
		n = n >> 1;
	}
	return count;
}

bool cmp(const pair<string, int>& a, const pair<string, int>& b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second > b.second;
}

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

	for (int i = 0; i < course.size(); i++) {
		course_check[course[i]] = true;
	}

	// 각 order의 모든 set 집합을 구한다.
	// 단 set의 크기가 course 집합 중 하나여야 한다.
	map<string, int> myMap[11];
	for (int i = 0; i < orders.size(); i++) {
		string sorted_string = sort_string(orders[i]);

		for (int j = 3; j < (1 << orders[i].size()); j++) {
			string s;

			int set_size = countBit(j);
			if (set_size == 1 || course_check[set_size] == false) continue;
			
			for (int k = 0; k < orders[i].size(); k++) {
				if ((1 << k) & j) {
					s += sorted_string[k];
				}
			}

			if (myMap[set_size].count(s) == 0) {
				myMap[set_size][s] = 1;
			}
			else {
				myMap[set_size][s]++;
			}
		}
	}

	for (int i = 0; i < course.size(); i++) {
		if (myMap[course[i]].size() == 0) continue;
		vector<pair<string, int>> result_vector(myMap[course[i]].begin(), myMap[course[i]].end());
		sort(result_vector.begin(), result_vector.end(), cmp);

		int max_value = result_vector[0].second;
		if (max_value <= 1) continue;
		for (int j = 0; j < result_vector.size(); j++) {
			if (result_vector[j].second == max_value) {
				answer.push_back(result_vector[j].first);
			}
			else {
				break;
			}
		}
	}

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

int main() {
	vector<string> orders = { "ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD" };
	vector<int> course = { 2, 3, 5 };
	solution(orders, course);

	return 0;
}