[프로그래머스] 메뉴 리뉴얼 - 2021 KAKAO BLIND RECRUITMENT

처음에 조합 리스트를 어떻게 구해야할지 몰라서 굉장히 막막했었는데, C++에서 제공하는 next_permutation 함수를 이용하면 순열 및 조합을 구할 수 있다는 걸 알고 내가 한 번 짜봤다. 이 문제에서의 핵심은 문자열로부터 조합을 구할 수 있느냐 없느냐의 차이인 것 같다. 조합만 구할 줄 안다면, 그 이후의 문제는 너무 쉽다.

 이것 저것 찾아보니 조합을 구하는 방법 두 가지를 알게 됐다. 첫 번째 방법은 위에서 말한 대로 next_permutation 함수를 이용해서 구하는 것이고, 두 번째는 DFS(또는 재귀)로 구하는 방법이다.

 

#1 next_permutation() 활용 풀이

 우선 내가 푼 코드는 next_permutation 함수를 사용해서 푼 방식이니 내 코드부터 설명을 해보겠다.

 

#include <bits/stdc++.h>

using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
    
    //사이즈 별 주문 수 + 코스 이름
    map<int, vector<pair<int, string>>> courseVec;

    //사이즈 별 가장 많은 주문 수 저장 벡터
    map<int, int> maxOrder;

    for (auto i : course) {
        maxOrder[i] = 0;
    }

    for (auto order : orders) {
        
        sort(order.begin(), order.end());

        for (int i = 0; i < course.size(); i++) {
            if (order.length() < course[i]) continue;

            vector<bool> v(order.length() - course[i], false);
            v.insert(v.end(), course[i], true);

            do {
                string tmp = "";
                for (int j = 0; j < v.size(); j++) {
                    if (v[j]) tmp += order[j];
                }

                bool isInCourse = false;
                for (int j = 0; j < courseVec[course[i]].size(); j++) {
                    if (courseVec[course[i]][j].second == tmp) {
                        isInCourse = true;
                        courseVec[course[i]][j].first++;

                        if (maxOrder[course[i]] < courseVec[course[i]][j].first)
                            maxOrder[course[i]] = courseVec[course[i]][j].first;
                    }
                }

                if (!isInCourse) {
                    courseVec[course[i]].push_back({ 1, tmp });
                }

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


        }
    }

    vector<string> answer;
    for (int i = 0; i < course.size(); i++) {
        for (int j = 0; j < courseVec[course[i]].size(); j++) {
            if (maxOrder[course[i]] == courseVec[course[i]][j].first) 
                answer.push_back(courseVec[course[i]][j].second);
        }
    }

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

전체적으로 쓰이는 변수는 maxOrder와 courseVec 두 변수를 이용했다.

• maxOrder : 조합의 크기 별로, 가장 많은 주문횟수를 저장하는 map
• courseVec : 조합의 크기 별로, 주문 수와 그에 해당하는 코스 이름을 저장한다. (변수 이름이 마땅히 생각이 안나서 그냥 막 지었다 ㅎㅎ)

가장 중요한 조합을 구하는 방법으로 next_permutation 함수를 이용했다. 이는 다른 블로그와 C++ Reference를 참고해서 작성했다. next_permutation은 순열을 구하는 데 사용되지만 조합을 구하는 데에도 응용해서 사용할 수 있다. 주의해야할 점은 next_permutation은 오름차순으로 정렬된 곳에서만 쓰일 수 있다. 그러므로 next_permutation 사용 전에는 항상 sort를 사용해주도록 하자.

 

 for (int i = 0; i < course.size(); i++) {
    if (order.length() < course[i]) continue;

    vector<bool> v(order.length() - course[i], false);
    v.insert(v.end(), course[i], true);

    do {
        string tmp = "";
        for (int j = 0; j < v.size(); j++) {
            if (v[j]) tmp += order[j];
        }

        bool isInCourse = false;
        for (int j = 0; j < courseVec[course[i]].size(); j++) {
            if (courseVec[course[i]][j].second == tmp) {
                isInCourse = true;
                courseVec[course[i]][j].first++;

                if (maxOrder[course[i]] < courseVec[course[i]][j].first)
                    maxOrder[course[i]] = courseVec[course[i]][j].first;
            }
        }

        if (!isInCourse) {
            courseVec[course[i]].push_back({ 1, tmp });
        }

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

bool형 v 벡터에 주문 문자열의 길이에서 조합의 크기를 뺀 만큼 false를 삽입하고, 이후에 조합의 크기만큼 true를 v 벡터 뒤에 삽입한다.

• 만약 구하고자 하는 조합의 크기가 2(ex: "AC", "BC"...)이고 주문 문자열의 길이가 5라면, v벡터에는 3개의 false(0)가 삽입되고 2개의 true(1)가 뒤에 삽입된다. 가장 중요한 포인트인 next_permutation에서 순열을 돌리는 벡터에 v벡터를 인자로 넘기면, false(0)과 true(1)로만 구성된 v벡터의 순열들을 구해준다. v 벡터에는 false과 true만을 요소로 가지기 때문에 순열의 중복을 제거해줄 수 있다. 이제 v[index]가 true일 때에만 order[index]를 조합 문자열 tmp에 더해주면 해당 주문 문자열에 대한 조합들을 모두 구할 수 있게 된다.

그렇게 모든 조합을 구하면 이제 문제는 간단하다. "maxOrder[조합 크기] = 해당 조합 크기의 주문 중 가장 많은 주문 횟수" 로 해당 조합의 크기를 가지는 조합 중 가장 많은 주문 횟수를 가지는 조합의 주문 횟수를 저장한다. 그리고 courseVec 변수에서는 조합 크기 별로 주문 횟수와 코스 이름을 저장한다.

나중에 answer 변수에는 courseVec에서 maxOrder 변수를 통해 저장되어 있는 가장 많은 주문 횟수를 가져와서 courseVec에서 코스이름들만 뽑아서 answer변수에 삽입해준 뒤 return 한다.

 

 

#2 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;
}

다른 블로그에서 가져온 DFS(재귀)를 활용해서 푼 풀이법인데, next_permutation 활용한 풀이법보다 훨씬 깔끔한 것 같아서 가져왔다.. ㅎㅎ

한 문제의 여러 풀이법을 알고 있으면 다른 비슷한 유형의 문제에서 하나의 풀이법만을 고집하지 않고 유연하게 대처할 수 있으니까 많은 풀이법을 알아두는 것도 PS 공부에 좋은 방법인 것 같다.

 

 

 

Reference

• C++ Reference
• https://notepad96.tistory.com/entry/C-%EC%A1%B0%ED%95%A9Combination-%EA%B5%AC%ED%95%98%EA%B8%B0
• https://ansohxxn.github.io/programmers/82/