[Programmers] (2021 KAKAO BLIND RECRUITMENT) Lv 2. 메뉴 리뉴얼

https://school.programmers.co.kr/learn/courses/30/lessons/72411

프로그래머스

 

cpp

닫기 줄바꿈

#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

void combination(set<string>& set, const string& str, string res, int r, int next) {
​​​​if (res.length() == r) {
​​​​​​​​set.insert(res);
​​​​​​​​return;
​​​​}

​​​​for (int i = next; i < str.length(); i++) {
​​​​​​​​res += str[i];
​​​​​​​​combination(set, str, res, r, i + 1);
​​​​​​​​res.pop_back();
​​​​}
}

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

​​​​// course의 값 순대로 알파벳에 대한 모든 조합을 구한다.
​​​​// 구해진 조합을 알파벳 순으로 정렬하고 그 개수를 보관한다. (매번 최대 개수와 비교해서 갱신)
​​​​
​​​​for (const auto& combi : course)
​​​​{
​​​​​​​​set<string> set; // 중복 단어 필터링하기 위해 set 사용

​​​​​​​​// course에 맞게 단어 조합
​​​​​​​​for (auto& str : orders)
​​​​​​​​{
​​​​​​​​​​​​::sort(str.begin(), str.end());
​​​​​​​​​​​​combination(set, str, "", combi, 0);
​​​​​​​​}

​​​​​​​​size_t maxCnt = 0;
​​​​​​​​vector<string> temp;

​​​​​​​​// 조합된 단어가 orders에 2개 이상있는지 체크
​​​​​​​​for (auto combiStr : set) 
​​​​​​​​{
​​​​​​​​​​​​size_t cnt = 0;

​​​​​​​​​​​​for (const auto& str : orders)
​​​​​​​​​​​​{
​​​​​​​​​​​​​​​​bool check = true;
​​​​​​​​​​​​​​​​for (const auto& word : combiStr)
​​​​​​​​​​​​​​​​{
​​​​​​​​​​​​​​​​​​​​if (str.find(word) == std::string::npos) {
​​​​​​​​​​​​​​​​​​​​​​​​check = false;
​​​​​​​​​​​​​​​​​​​​​​​​break;
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​}

​​​​​​​​​​​​​​​​if (check) ++cnt;
​​​​​​​​​​​​}

​​​​​​​​​​​​if (cnt >= 2 && maxCnt <= cnt)
​​​​​​​​​​​​{
​​​​​​​​​​​​​​​​if (maxCnt < cnt) 
​​​​​​​​​​​​​​​​​​​​maxCnt = cnt, temp.clear();

​​​​​​​​​​​​​​​​temp.emplace_back(combiStr);
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​answer.insert(answer.end(), temp.begin(), temp.end());
​​​​}

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

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/commit/01c2da1e65a49ba6604723207af5126d04fd9f40

[level 2] Title: 메뉴 리뉴얼, Time: 0.83 ms, Memory: 4.22 MB -BaekjoonHub · developeSHG/Algorithm-Baekjoon_Programmers@01c