알고리즘(C++) / 프로그래머스 level 2 : 메뉴 리뉴얼

level 2 : 메뉴 리뉴얼

https://programmers.co.kr/learn/courses/30/lessons/72411?language=cpp# 

코딩테스트 연습 - 메뉴 리뉴얼

 

내 코드

//프로그래머스 메뉴 리뉴얼
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>

using namespace std;

bool cmp(const pair<string, int>& a, const pair<string, int>& b) {
    if(a.first.size() == b.first.size())
        return a.second > b.second; //조합 순으로 내림차순 정렬
    return a.first.size() > b.first.size(); //string size 내림차순
}

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

    for (int i = 0; i < orders.size(); i++) {
        sort(orders[i].begin(), orders[i].end());
    }

    for (int i = 0; i < orders.size(); i++) {
        //비트 마스킹
        for (int j = 1; j < (1 << orders[i].size()); j++) {
            string menu = "";
            for (int k = 0; k < orders[i].size(); k++) {
                if (j & (1 << k)) {
                    menu += orders[i][k]; //조합 구성
                }
            }
            for (int l = 0; l < course.size(); l++) {
                if (course[l] == menu.size()) {
                    m[menu] += 1; // 구성 1증가
                    break;
                }
            }
        }
    }

    vector <pair<string, int>> vec(m.begin(), m.end()); //map vector로 copy

    sort(vec.begin(), vec.end(), cmp); //정렬

    int string_size = 20; //최대
    int string_count = 0;
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i].second == 1) //조합이 한개 있을 때
            continue;
        if (string_size > vec[i].first.size()) { //string 중 가장 최대 조합
            string_size = vec[i].first.size();
            string_count = vec[i].second;
            answer.push_back(vec[i].first);
            continue;
        }
        if (string_count == vec[i].second) //최대 조합 개수가 같을때
            answer.push_back(vec[i].first);
    }

    sort(answer.begin(), answer.end()); //출력 정렬
    return answer;
}

int main() {
    vector<string> orders = { "ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH" };
    vector<int> course = { 2,3,4 };
    solution(orders, course);
    return 0;
}

 

설명

https://algosu.tistory.com/97 에서 풀이를 참고하여 문제를 해결하였다. 

• orders에서의 string 에서 여러 조합을 알아낼 수 있다. 이 조합 중 size가 course 값과 같으면 map의 값을 1 증가한다. 
• 이때 조합은 비트마스킹을 이용하여 모든 조합을 뽑아낼 수 있었다. 
• map을 vector 형태를 바꿔 string 사이즈 순으로 조합의 순으로 정렬한다. 
• string의 사이즈가 같은 것 중에서 1이 아닌 가장 큰 string을 answer에 저장한다.
• answer을 오름차순으로 정렬한다. 

 

다른 사람 풀이

//프로그래머스 메뉴 리뉴얼
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

map <string, int> m;

void combination(string order, string s, int n) {
    if (s.size() == n)
        m[s]++;
    else {
        for (int i = 0; i < order.size(); i++) {
            combination(order.substr(i + 1), s + order[i], n);
        }
    }
}

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

    for (int i = 0; i < orders.size(); i++) {
        sort(orders[i].begin(), orders[i].end());
    }//order정렬

    for (int i = 0; i < course.size(); i++) {
        for (int j = 0; j < orders.size(); j++) {
            combination(orders[j], "", course[i]);
        }
        int num = 0;
        for (auto it : m) {
            num = max(num, it.second);
        }
        for (auto it : m) {
            if (num >= 2 && it.second == num)
                answer.push_back(it.first);
        }
        m.clear();
    }

    return answer;
}

int main() {
    vector<string> orders = { "ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH" };
    vector<int> course = { 2,3,4 };
    solution(orders, course);
    return 0;
}

 

설명

• course의 수 만큼 조합을 구한다. (combination() 함수)
• course개의 모든 조합 중 가장 많이 나온 조합을 찾아서 출력한다.
• 이를 course번 반복한다. 

 

고찰

이번 문제에서 꽤 많은 시간과 노력을 쏟았다. 적어도 3시간은 걸린듯 하다.

조합을 저번에 후보키에서 푼 문제처럼 비트마스킹을 이용하였다. 비트마스킹을 이용하면 모든 조합을 얻어낼 수는 있지만 n개의 조합만 선택적으로 얻을 수는 없다. 다른 사람들이 푼 문제를 보면 combination 함수를 만들어 n 사이즈의 조합을 구할 수 있다.

어떻게 조합을 구하면 좋을지 생각하여 조합을 구해야할 거 같다.