⚙️ 알고리즘 분류 : 완전 탐색
🔠 언어 : c++
🤫 힌트.
bit mask와 비슷하게 생각해보자!
✏️ 풀이.
문제 이해를 잘 해야했다.
- 각
알파벳은 단품요리고, 각문자열은 코스요리다. - 고객이 추천한 코스요리를 분해하여 새로운 코스요리를 만들 수 있다.
- course는 주방장이 원하는 코스요리의 길이인데, 만약 조건을 충족하는 코스요리가 없다면 꼭 그 길이의 코스요리를 포함할 필요는 없다.
문제 풀이 단계 - 코드에 표시했어요!
1) 알파벳으로 해체될 문자열을 orders에서 하나 선정한다.
2) 문자열의 길이와 같은 길이의 bool type vector를 선언한다. 이때, 초기값은 모두 true로 선언한다.
=> bool vector[3] = [true, true, true]
3) course에서 값을 하나 선정해서, bool vector에서 그 값만큼 false로 바꾼다.
=> 만약 알파벳 2개의 문자열을 만든다면, bool vector[3] = [false, false, true]
4) bool vector를 next_permutation에 넣어서 false 값이 여러 자리에 고루 배치되게끔 한다.
=> [false, false, true], [false, true, false], [true, false, false]
5) bool vector에서 한 index의 value가 false일 때, 문자열에서 같은 index에 위치한 알파벳을 구한다.
=> 고객이 추천한 문자열이 AGB이고 vector가 [false, true, false]라면, AB라는 새 문자열이 나온다.
6) 많이 나온 문자열의 순서대로 정렬한다.
7) 각 문자열의 길이 중에서 가장 많이 나온 문자열을 answer에 담는다.
➡️ 2)에서 true로 초기화 하는 이유
bool type을 출력하면 ture는 1, false는 0이 나온다.
next_permutation을 쓸 땐 반드시 오름차순으로 정렬을 해주어야 한다.
만약 [true, false, false]를 출력하면 [1,0,0]이므로 오름차순 정렬이 아니다.
오름차순을 만들기 위해서 모두 true로 만들고 앞에서부터 필요한 만큼 false를 해준다.
왜 true로 초기화해야 하는지 오늘 알았다...
⚠️ 헤맨 부분.
orders의 각 문자열을 정렬해줬어야 했는데 정렬해주지 않아서 계속 틀렸다.
문제에서 '배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.' 라는 문장이 정렬해줘야 하는 증거다.
👩🏻💻 코드.
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define mp make_pair
using namespace std;
map<string, int> m;
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;
// 1)
for(int i=0; i<orders.size(); i++){
string target=orders[i];
// 문자열 정렬 중요!!
sort(target.begin(), target.end());
// 2)
vector<bool> mask(target.size(), true);
for(int j=0; j<course.size(); j++){
int iter=course[j];
if(target.size()<iter) continue;
// 3)
for(int k=0; k<iter; k++) mask[k]=false;
do{
string str="";
for(int k=0; k<mask.size(); k++){
// 5)
if(!mask[k]) str+=target[k];
}
m[str]++;
// 4)
}while(next_permutation(mask.begin(), mask.end()));
}
}
// 6)
vector<pair<string,int>> cand;
for(auto it=m.begin(); it!=m.end(); it++) cand.push_back(mp(it->first, it->second));
sort(cand.begin(), cand.end(), cmp);
for(int i=0; i<course.size(); i++){
// 최소 2명에게 추천받아야 하므로!
int mx_cnt=2;
for(int j=0; j<cand.size(); j++){
if(cand[j].first.length()!=course[i]) continue;
// 7)
if(mx_cnt<=cand[j].second){
mx_cnt=cand[j].second;
answer.push_back(cand[j].first);
}
}
}
sort(answer.begin(), answer.end());
return answer;
}😎 후기.
다른 문제에서도 같은 풀이를 많이 적용할 수 있었던 문제다. 이것도 정말 잘 만든 문제! 처음에 풀 땐 답지를 봤는데, 그때 답 보고 정말 충격받았다... 이렇게도 풀 수 있구나 싶었던...! 정말 잘 만든 문제다.
코테 준비하면 한 번 풀어볼만한 문제.
