62★★★] 카카오 블라인드 / 메뉴 리뉴얼 /C++

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

 

1. 각 단품메뉴 개수(course)별로

2. 각 손님들이 주문한 단품메뉴 리스트(order)에서 만들 수 있는 조합과 그 조합이 나온 횟수를 구하고,

    - 조합을 구하는 방법은 0과 1로 이뤄진 벡터(선택할 메뉴개수 = 1의 개수)를 next_permutation돌려서

    - 1인 문자열을 map에 넣는 식으로 했습니다. // 설명하기도 힘든 어려븐 문제 

 

3. 횟수로 정렬해서 

4. 최대값인 문자열만 answer에 넣습니다.

 

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

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

vector<string> solution(vector<string> order, vector<int> course) {
	vector<string>ans;
	// ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]
	// [2,3,4]
	
	// 코스별로 제일 많이 나온것만 ans에 넣기 
	for (int i = 0; i < course.size(); i++) {

		// 각 조합이 나온 횟수 저장하는 map
		map<string, int>cmb;

		// 각 오더별로 모든 조합 구하기 
		for (int j = 0; j < order.size(); j++) {

			// 주문이 코스길이보다 길때만 가능한 조합 계산
			if (course[i] <= order[j].size()) {
				vector<int>v;
				// 1이면 해당 문자열 선택
				// course만큼만 1 입력 
				for (int k = 0; k < course[i]; k++) {
					v.push_back(1);
				}
				for (int k = 0; k < order[j].size() - course[i]; k++) {
					v.push_back(0);
				}
				sort(v.begin(), v.end());
				do {
					
					string s = "";
					for (int p = 0; p < v.size(); p++) {
						if (v[p] == 1) {
							s += order[j][p];
						}
					}

					// 선택된 조합 
					// 정렬해주고 
					// map에 나온 횟수 ++
					sort(s.begin(), s.end());
					cmb[s]++;		

				} while (next_permutation(v.begin(), v.end()));

			}


		}

		// 여기까지 정해진 코스 숫자에 나올 수 있는 모든 조합이 정해짐
		// 이걸 나온 횟수에 따라 정렬해야함 

		// map은 sort안되니까 vector로 옮김 
		// 근데 모든 order가 course보다 작으면 map에 아무것도 없을 수 있기 때문에 조심.
		if (cmb.size() > 0) {
			vector<pair<string, int>>vec(cmb.begin(), cmb.end());
			// 벡터를 정렬함
			sort(vec.begin(), vec.end(), cmp);

			// 정렬 후 최대값인 문자열만 ans에 넣기
			// 최대값은 2이상이어야함
			int max = vec[0].second;
			if (max >= 2) {
				for (int q = 0; q < vec.size(); q++) {
					if (vec[q].second == max) {
						ans.push_back(vec[q].first);
					}

				}

			}

		}		
		

	}


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

 

https://henrynoh.tistory.com/75

메뉴 리뉴얼 C++ 2021 KAKAO Blind Recruitment

 

https://twpower.github.io/82-next_permutation-and-prev_permutation

[Algorithm] C++에서 next_permutation 함수(혹은 prev_permutation 함수)를 통해서 순열 구하기

https://mjmjmj98.tistory.com/38

[C++ / Algorithm] 순열(next_permutation) 사용 방법과 조합(Combination) 구하기