[C++로 풀이] 메뉴 리뉴얼 (DFS, 조합)⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 메뉴 리뉴얼
난이도 ⭐⭐
🚀 문제
🚀 내 풀이 ⭕ (DFS로 조합 구하기)
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
bool cmp(pair<string, int> a, pair<string, int> b){
return a.second > b.second;
}
void DFS(map<string, int>& dic, string& order, string comb, int index, int depth) {
if (depth == comb.length()) {
dic[comb]++;
return;
}
for (int i = index; i < order.length(); i++) {
comb[depth] = order[i];
DFS(dic, order, comb, i + 1, depth + 1);
}
}
vector<string> solution(vector<string> orders, vector<int> course) {
vector<string> answer;
map<string, int> dic;
for (int i = 0; i < orders.size(); i++) {
sort(orders[i].begin(), orders[i].end());
for (int j = 0; j < course.size(); j++) {
string comb = "";
comb.resize(course[j]);
DFS(dic, orders[i], comb, 0, 0);
}
}
vector<pair<string, int>> sorted;
for (auto& order : dic)
if (order.second > 1)
sorted.push_back(make_pair(order.first, order.second));
sort(sorted.begin(), sorted.end(), cmp);
for(int i = 0; i < course.size(); i++){
int max = 0;
for(int j = 0; j < sorted.size(); j++){
if (sorted[j].first.length() != course[i])
continue;
else if (max == 0){
answer.push_back(sorted[j].first);
max = sorted[j].second;
}
else if (max == sorted[j].second)
answer.push_back(sorted[j].first);
else
break;
}
}
sort(answer.begin(), answer.end());
return answer;
}
먼저 문제에 대한 해답을 얻기 전에, 각 메뉴별로 가능한 모든 조합을 만들어 봅니다.
예를 들어 “ABCD”의 경우 다음과 같이 11가지 조합이 가능합니다.
- “AB”, “AC”, “AD”, “BC”, “BD”, “CD”, “ABC”, “ABD”, “ACD”, “BCD”, “ABCD”
위와 같이 각 메뉴에서 가능한 모든 조합을 만들었다면, 각 조합의 개수를 세면 됩니다.
이때 “ABC”와 “CBA”를 같은 조합으로 세는 점을 주의해야 합니다.
쉽게 해결하는 방법으로는 처음에 각 문자열을 알파벳 순서로 정렬하거나, 만들어진 조합 문자열을 정렬하는 방법이 있겠습니다.
각 조합별로 개수를 셌다면, 최종적으로 문자열의 길이가 같은 조합 중 가장 많이 나타난 조합은 무엇인지 찾으면 됩니다.
출처 : Kakao Tech 2021 카카오 신입 공채 1차 코테 문제 해설 https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/
이 문제는 어떻게 풀어야할지 감을 전혀 못 잡겠어서 Kakao Tech 사이트에 찾아가 위와 같은 해설을 본 후 풀이를 할 수 있었다.ㅠㅠ 그냥 조합을 다 구해서 카운팅 하는거구나..!
1️⃣ 모든 조합 구하고 조합 종류에 따른 카운팅하기 (map에 저장)
void DFS(map<string, int>& dic, string& order, string comb, int index, int depth) {
if (depth == comb.length()) {
dic[comb]++;
return;
}
for (int i = index; i < order.length(); i++) { // order의 index부터
comb[depth] = order[i];
DFS(dic, order, comb, i + 1, depth + 1); // index에 i+1를 넘김. ⭐즉, 다음 문자부터 DFS 시작 (중복 허용 X)⭐
}
}
vector<string> solution(vector<string> orders, vector<int> course) {
vector<string> answer;
map<string, int> dic;
for (int i = 0; i < orders.size(); i++) {
sort(orders[i].begin(), orders[i].end());
for (int j = 0; j < course.size(); j++) {
string comb = "";
comb.resize(course[j]);
DFS(dic, orders[i], comb, 0, 0);
}
}
- 1️⃣ 조합에선 “AB”나 “BA”나 동일한 것이기 때문에 이를 고려하여 먼저
orders의 모든 문자열을 사전순으로 정렬한 후 진행한다. - 2️⃣
orders의 원소들(string)마다course의 원소들에 해당하는 수의 모든 조합을 구한다.- 예를 들어
course가 [2, 3, 4]이라면 “ABCD” 주문에서 얻을 수 있는 조합의 종류는- 2 👉 “AB”, “AC”, “AD”, “BC”, “BD”, “CD”
- 3 👉 “ABC”, “ABD”, “ACD”, “BCD”
- 4 👉 “ABCD”
depth가 고정적인comb의 길이(=course[j])에 도달하면 해당 조합이 완성되어 DFS 종료.- DFS 순서
course[j]가 2 라면- “A”👉”AB” (재귀종료)
- “A”👉”AC” (재귀종료)
- “A”👉”AD” (재귀종료)
- “B”👉”BC” (재귀종료)
- “B”👉”BD” (재귀종료)
- “C”👉”CD” (재귀종료)
course[j]가 3 라면- “A” 👉 “AB” 👉 “ABC” (재귀종료)
- “A” 👉 “AB” 👉 “ABD” (재귀종료)
- “A” 👉 “AC” 👉 “ACD” (재귀종료)
- “B” 👉 “BC” 👉 “BCD” (재귀종료)
- 예를 들어
- 3️⃣ 하나의 string
orders[i]에서 구한 모든 조합 문자열을 map 의 Key 로 추가한다. 그리고 Value는 이 조합 문자열이 모든 orders 를 돌면서 등장한 횟수가 저장될 것이다.- 3 번째 예제의
orders로 진행했다면dicmap의 상태- dic[“AW”] = 1; dic[“AWX”] = 1; dic[“AX”] = 1; dic[“WX”] = 2; dic[“WXY”] = 1; dic[“WY”] = 1; dic[“XY”] = 2; dic[“XYZ”] = 1; dic[“XZ”] = 1; dic[“YZ”] = 1;
- 3 번째 예제의
- 4️⃣ DFS(dic, orders[i], comb, 0, 0); 은 곧 nCr 조합을 구하는 과정인데, 여기서 n이
order[i].length()가 되고 r 이course[j]가 된다.
(C++) 조합(Combination)을 구현하는 여러가지 방법
2️⃣ map 을 vector 로 옮기고 value(등장한 횟수)별로 내림차순 정렬 (가장 많이 등장한게 가장 앞에 오게끔)
bool cmp(pair<string, int> a, pair<string, int> b){
return a.second > b.second;
}
//...
vector<pair<string, int>> sorted;
for (auto& order : dic)
if (order.second > 1)
sorted.push_back(make_pair(order.first, order.second));
sort(sorted.begin(), sorted.end(), cmp);
가장 많이 등장한 조합을 메뉴로 삼을 것이기 때문에 Value에 의한 내림차순 정렬을 진행해야 한다. map 자체는 Key에 의한 정렬밖에 안되기 때문에 vector에 map의 원소들을 pair 원소로 옮긴 후 이를 Value인 order.second에 의해 내림차순 정렬 시킨다.
그리고 어차피 1 번 밖에 등장하지 않은 조합 문자열(주문 조합)들은 2 번 이상 나오지 않은 것이므로 vector에 넣지 않았다.
3 번째 예제의 orders로 진행했다면 dic map의 상태를 위와 같이 정렬한 이후 sorted의 상태 👉 (“WX”, 2) (“XY”, 2)
3️⃣ 내림 차순 정렬된 것의 최대값에 해당하는 것들 answer에 삽입
for(int i = 0; i < course.size(); i++){
int max = 0;
// 메뉴 수가 course[i]인 것의 최다 등장 메뉴 조합들 구하기
for(int j = 0; j < sorted.size(); j++){
if (sorted[j].first.length() != course[i])
continue;
else if (max == 0){ // 최대값 첫 등장 (max에 이를 저장)
answer.push_back(sorted[j].first);
max = sorted[j].second;
}
else if (max == sorted[j].second) // 최대값이 여러개일 경우를 대비하여 (max와 일치하면)
answer.push_back(sorted[j].first);
else // 이제 최대값에 해당하지 않는다면 break
break;
}
}
sort(answer.begin(), answer.end());
course원소, 즉 메뉴 수별로 최대값을 저장해야하며- 최대값이 여러개일 경우 그 메뉴들도 전부 추가한다.
예를들어 예제 1의 경우 메뉴 4개의 조합 같은 경우 최대 등장 횟수가 “ACDE”, “BCFG”가 동일하다. 그러므로 둘 다 answer에 추가가 되야 한다. “ACDE” 는 첫번째 else if를 통해 추가될 것이고 “BCFG”는 첫 등장이 아니므로 두번째 else if를 통해 추가될 것.
- 문자열 원소 자체들은 정렬되어 있지만 전체적인 정렬도 해주기 위해 마지막으로 한번 더
answer를 정렬
🚀 다른 풀이 (next_permutation으로 조합 구하기)
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
bool cmp(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;
map<string, int> dic;
for (int i = 0; i < orders.size(); i++) {
sort(orders[i].begin(), orders[i].end());
for (int j = 0; j < course.size(); j++) {
if (course[j] > orders[i].length())
continue;
vector<bool> temp(orders[i].length(), true);
for(int k = 0; k < course[j]; k++)
temp[k] = false;
do{
string str = "";
for(int k = 0; k < orders[i].length(); k++)
if (temp[k] == false)
str += orders[i][k];
dic[str]++;
}while(next_permutation(temp.begin(), temp.end()));
}
}
vector<pair<string, int>> sorted;
for (auto& order : dic)
if (order.second > 1)
sorted.push_back(make_pair(order.first, order.second));
sort(sorted.begin(), sorted.end(), cmp);
for(int i = 0; i < course.size(); i++){
int max = 0;
for(int j = 0; j < sorted.size(); j++){
if (sorted[j].first.length() != course[i])
continue;
else if (max == 0){
answer.push_back(sorted[j].first);
max = sorted[j].second;
}
else if (max == sorted[j].second)
answer.push_back(sorted[j].first);
else
break;
}
}
sort(answer.begin(), answer.end());
return answer;
}
// nCr 조합 👉 여기서 n은 orders[i].length()가 되고 r은 course[j]가 된다.
for (int i = 0; i < orders.size(); i++) {
sort(orders[i].begin(), orders[i].end());
for (int j = 0; j < course.size(); j++) {
if (course[j] > orders[i].length()) // 이거 안해주면 밑에서 런타임 에러가 발생한다!! nCr에 있어서 r이 n보다 크면 안된다. 예를 들어 주문 3개밖에 안했는데 4개 짜리 조합 생성하려는 경우 방지
continue;
vector<bool> temp(orders[i].length(), true);
for(int k = 0; k < course[j]; k++) // 앞의 r개를 false로 하기로 했다.
temp[k] = false;
do{
string str = "";
for(int k = 0; k < orders[i].length(); k++)
if (temp[k] == false)
str += orders[i][k];
dic[str]++;
}while(next_permutation(temp.begin(), temp.end()));
}
}
next_permutation으로 조합을 구현하는 자세한 설명은 이 포스트 참고 (이 포스트에서 내가 한 방법은 아래 방법이다. 순서대로 조합되도록 한 것.)
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기