2021 KAKAO BLIND RECRUITMENT > 메뉴 리뉴얼

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/72411

프로그래머스

이 문제도 모든 조합을 판별해야는 문제이다.

 

따라서 조합을 만드는 부분에 있어서는 백트래킹 비법을 사용하는데 이는 

https://unlock546.tistory.com/410

완전탐색 > 소수 찾기

에서 풀었던 내용과 거의 동일하다.

 

차이점이라면 이 문제에서는 조합된 결과들을 길이에 따라 분리하여 그 중 가장 많이 등장한 것을 찾아야 한다는 점이다.

 

따라서, 가장 큰 반복문에 있어서 course 를 순회하며 orders에 주어진 문자열들에서 n 길이의 조합을 모두 찾아낸 다음 그 들 중 최다 등장을 답에 추가하는 방식으로 구현하였다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

void generateCombinations(const string& order, int course_size, int start, string current, map<string, int>& candidates){
    if(current.size()==course_size){
        sort(current.begin(), current.end());
        candidates[current]++;
        return;
    }
    
    for(int i = start; i<order.size();++i){
        generateCombinations(order, course_size, i+1, current+order[i], candidates);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for (int course_size : course) {
        map<string, int> candidates;
        
        // 각 주문에 대해 조합 생성
        for (string order : orders) {
            generateCombinations(order, course_size, 0, "", candidates);
        }
        
        // 가장 높은 빈도를 찾음
        int max_count = 0;
        for (const auto& candidate : candidates) {
            if (candidate.second > max_count) {
                max_count = candidate.second;
            }
        }
        
        // 가장 높은 빈도의 조합을 결과에 추가
        for (const auto& candidate : candidates) {
            if (candidate.second == max_count && max_count > 1) {
                answer.push_back(candidate.first);
            }
        }
    }
    
    // 결과를 정렬하여 반환
    sort(answer.begin(), answer.end());
    return answer;
}