문제
Link
간략한 문제 설명
- orders : 손님들의 주문 목록
- course : 만들고자 하는 코스의 요리 개수
위와 같이 orders와 course가 입력으로 주어진다.
문제에서 요구하는 것은, 손님들의 order를 보고 조건을 만족하는 새로운 코스메뉴들을 만드는 것이다.
첫번째 입력을 예로들면 course가 [2,3,4] 이므로 orders를 검사하여 2개, 3개, 4개로 만들 수 있는 새로운 코스메뉴를 모두 찾아 result에 저장하는 것이다.
풀이
필요 정보
새로운 코스메뉴의 조건은 최소 2명이상의 손님에게 주문 된 구성이어야 한다.
위 조건을 검사하기 위해서는 우선 course의 개수에 맞는 모든 메뉴의 조합들을 찾아야 한다.
그리고 각 구성마다 몇 명의 손님이 주문했는지 알아야한다.
조합은 재귀함수를 통해 구현하고 찾은 메뉴 조합의 개수는
map을 통해 카운트 해야겠다는 생각이 들었다.
손님의 order 마다 course 개수에 맞는 구성을 모두 찾고 이를 map에 {key: 메뉴조합, value: 개수} 의 형식으로 저장하면 된다.
그리고 map이 key 값으로 정렬 될 필요는 없으므로 unordered_map을 사용했다. 물론 나중에 value 값으로 정렬을 해줘야 한다.
메뉴의 조합 찾기
아래의 findCourse 라는 재귀함수를 통해 course 개수에 맞는 메뉴의 조합을 찾고 메뉴가 등장한 개수를 count 해줬다.
1
2
3
4
5
6
7
8
9
10
11
12
// c: course 개수
void findCourse(const string &order,unordered_map<string,int> &um,string curr,int L,int index, int c){
if(L==c){
um[curr]++;
return;
}
// 재귀 호출
for(int i=index;i<order.length();i++){
findCourse(order,um,curr+order[i],L+1,i+1,c);
}
}
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
void findCourse(const string &order,unordered_map<string,int> &um,string curr,int L,int index, int c){
if(L==c){
um[curr]++;
return;
}
for(int i=index;i<order.length();i++){
findCourse(order,um,curr+order[i],L+1,i+1,c);
}
}
bool compare(pair<string,int> a, pair<string,int> b){
return a.second > b.second;
}
vector<string> solution(vector<string> orders, vector<int> course) {
vector<string> answer;
for(const auto &c:course){
unordered_map<string,int> um;
for(auto order:orders){
sort(order.begin(),order.end());
findCourse(order,um,"",0,0,c);
}
if(um.empty())
continue;
// map을 value 기준 내림차순 정렬하기 위해 vector로 assign
vector<pair<string,int>> v(um.begin(),um.end());
sort(v.begin(),v.end(),compare);
// 가장 int 값이 큰 녀석들만 answer 배열에 추가
int std = v[0].second;
if(std>=2){
for(int i=0;i<v.size();i++){
if(v[i].second==std)
answer.push_back(v[i].first);
else
break;
}
}
}
// 오름차순 정렬
sort(answer.begin(),answer.end());
return answer;
}
