[프로그래머스/C++] 알고리즘 - 메뉴 리뉴얼

안녕하세요! 테크지니어22입니다.

오늘은 프로그래머스 알고리즘 메뉴 리뉴얼 을 풀어보도록 하겠습니다.

 

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

프로그래머스

 

[문제 접근]

orders의 최대크기 20, orders각 원소의 크기를 10, course =[2,3,4,5,6,7,8,9,10]라 가정하면

연산 개수는 약 20*(10C2+10C3+10C4+ ... 10C10) 으로 시간복잡도가 크지 않음을 알 수 있습니다.

그래서 완전탐색으로 접근했고, 조합을 이용하여 모든 경우를 고려한 후, 해시 맵에 저장하여 중복 개수를 세었습니다.

 

[풀이 전략]

1. orders의 원소를 오름차순으로 문자열 정렬을 합니다.

2. 각 orders의 원소마다 course의 원소만큼 뽑아서 map 넣습니다.
3. map에서 정답에 해당되는 것들 선별합니다.

- 최소 2명이상

- 가장 많이 함께 주문한 단품메뉴들이 여러개면 모두 출력 배열에 삽입

 

[코드]

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    unordered_map<string,int> m ; 
    for(auto cnt : course){
       for(auto order : orders){
        sort(order.begin(), order.end());
        int N = order.size();
        vector<int> a ;
        if(cnt > N) continue;
     for(int i = 0; i < N; ++i)  a.push_back(i < cnt ? 0 : 1);
    do{
    string s = "" ;
    for(int i = 0; i < N; ++i)
      if(a[i] == 0) {
          s += order[i];
      }
    m[s]++;
  }while(next_permutation(a.begin(), a.end()));
        
    }  
    int maxv = 0 ;
    vector<string> maxStr;
    for(auto e : m){
        if(e.second < 2) continue; 
        if(e.first.size() != cnt) continue;
        if(maxv < e.second){
            maxv = e.second;
            maxStr.clear();
            maxStr.push_back(e.first); 
        } else if(maxv == e.second){
            maxStr.push_back(e.first); 
        }
    }
    for(auto str : maxStr)  answer.push_back(str);

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

 

[배울 점]

- for문으로 구현하면서 초기화 문제 신경쓰기.