[프로그래머스] 메뉴 리뉴얼 C++ 풀이

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

프로그래머스

 

풀이 방법 (1) - 브루트포스

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
bool visit[26];
vector<char> v;
vector<pair<int,string>> res[10];
int mCnt[10];
void solve(int idx, int cnt, vector<string>& o, vector<int>& c, vector<string>& a)
{
    if(cnt>c[c.size()-1])
        return;
    
    for(int i=0;i<c.size();i++) // course 탐색
    {
        if(c[i]==cnt)
        {
            int rCnt=0; // 이 코스가 가능한 사람 개수
            for(int j=0;j<o.size();j++) // orders 탐색
            {
                int oCnt=0;
                for(int k=0;k<v.size();k++) // 뽑아낸 문자 탐색
                    for(int z=0;z<o[j].length();z++) // orders 하나하나 탐색
                        if(v[k]==o[j][z])
                            oCnt++;
                if(oCnt==v.size())
                    rCnt++;
            }
            if(rCnt>=2)
            {
                string str(v.begin(),v.end());
                res[i].push_back(make_pair(rCnt,str));
                mCnt[i]=max(mCnt[i],rCnt);
            }
            
            
        }
    }
    
    for(int i=idx;i<26;i++)
    {
        if(visit[i]==true)
        {
            v.push_back('A'+i);
            solve(i+1,cnt+1,o,c,a);
            v.erase(v.begin()+cnt);
        }
    }
    
}

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

    fill(visit,visit+26,false);
    for(int i=0;i<orders.size();i++)
        for(int j=0;j<orders[i].size();j++)
            visit[orders[i][j]-'A']=true;
    
    solve(0,0,orders,course,answer);
    
    for(int i=0;i<course.size();i++)
    {
        for(int j=0;j<res[i].size();j++)
        {
            if(res[i][j].first==mCnt[i])
                answer.push_back(res[i][j].second);
        }
    }
    
    sort(answer.begin(),answer.end());
    
    return answer;
}

이 풀이 방법에 대해서는 소스 코드까지 하나하나 설명은 생략하고 큰 틀에서만 설명하겠다...

MAP을 이용한 풀이가 좋기 때문이다.

먼저, 모든 손님들이 주문한 메뉴들을 통해서 주문 받은 메뉴만 표시를 한다.

그리고 주문 받은 메뉴들만 DFS를 통해 조합을 구현해 뽑아낸다. 즉, N개를 뽑아내는것이다.

뽑아낼때마다 course 를 탐색하며 내가 뽑아낸 N개가 course에 존재하는지 확인한다.

존재한다면 이렇게 뽑아낸 코스 메뉴를 2명 이상이 주문을 했는지 확인하고 주문한 사람의 수와 함께

코스메뉴를 기록함.

그 후, 코스 메뉴 N개를 뽑아내는 방법마다 탐색하며 주문한 사람의 수가 제일 많은 메뉴들만 answer에

담는다.

 

풀이 방법 (2) - MAP

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
map<string,int> m;
int maxCnt[11]; // 길이에 따른 cnt
bool visit[26];

string str;
void solve(int idx, int oIdx, vector<string>& o)
{
    for(int i=idx;i<26;i++)
    {
        if(visit[i]==true)
        {
        str+=(char)('A'+i);
        if(m.find(str)==m.end())
            m.insert(pair<string,int>(str,1));
        else
            m[str]++;
        maxCnt[str.length()]=max(maxCnt[str.length()],m[str]);
        solve(i+1, oIdx, o);
        str.pop_back();
        }
    }
    
}



vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(int i=0;i<orders.size();i++)
    {
        fill(visit,visit+26,false);
        for(int j=0;j<orders[i].length();j++)
            visit[orders[i][j]-'A']=true;
        solve(0,i,orders);
    }
    map<string,int>::iterator iter;
    
    for(int i=0;i<course.size();i++)
    {    
        for(iter=m.begin();iter!=m.end();iter++)
        {
            if(iter->second>=2&&iter->first.length()==course[i]
            &&iter->second==maxCnt[iter->first.length()])
                answer.push_back(iter->first);
        }
    }
    
    sort(answer.begin(),answer.end());
    return answer;
}

확실히 브루트포스보다 빠르다.

상세히 소스코드를 설명하기전 큰 틀로 MAP을 이용한 풀이방법을 설명하자면

orders 각각을 이용해 코스 메뉴의 조합을 구한다.

이때 MAP을 이용해 각 코스 메뉴의 조합이 나오는 횟수를 카운트한다.

그러면 각 코스에 대해 몇명이 단품메뉴로 주문했는지 횟수를 알 수 있다.

이제 소스코드를 설명하겠다.

 

map<string,int> m;
int maxCnt[11];
bool visit[26];

m은 string과 int로 구성되어있는데 string은 만들어진 코스메뉴요리, int는 만들어진 횟수이다.

maxCnt[i]는 길이i에 대해 최대 만들어진 횟수를 기록할거다.

visit[i]는 A~Z 메뉴가 있을텐데 각 손님이 주문한 메뉴를 표시할거다.

 

for(int i=0;i<orders.size();i++)
{
        fill(visit,visit+26,false);
        for(int j=0;j<orders[i].length();j++)
            visit[orders[i][j]-'A']=true;
        solve(0,i,orders);
}

orders i번째를 방문하여 이 주문에 포함된 단품메뉴를 표시한다.

이는 조합을 구할때 사용한 메뉴만을 이용해 구하기 위해서이다.

 

void solve(int idx, int oIdx, vector<string>& o)
{
	...
}

solve 함수는 현재 탐색중인 orders의 몇번째 메뉴인지를 나타내는 idx와 몇번째 orders를 탐색중인지인 oIdx로 구성.

 

for(int i=idx;i<26;i++)
{
        if(visit[i]==true)
        {
        str+=(char)('A'+i);
        cout<<str<<endl;
        if(m.find(str)==m.end())
            m.insert(pair<string,int>(str,1));
        else
            m[str]++;
        maxCnt[str.length()]=max(maxCnt[str.length()],m[str]);
        solve(i+1, oIdx, o);
        str.pop_back();
        }
}

메뉴는 A~Z이므로 for문을 0~25까지 돌게 했다.

이때 주문된 메뉴라면 str에 붙여넣는다. ( str은 현재 만들어진 코스메뉴를 나타낸다. )

그리고 만들어진 코스에 대해 존재하지 않는다면 map에 코스메뉴와 만들어진 횟수인 1을 넣는다.

만약 이미 만들어진 코스라면 만들어진 횟수에 +1을 해준다.

그리고 만들어진 str의 길이에 대해 maxCnt를 갱신할 수 있으면 갱신해주자.

 

그러면 결과적으로 map에는 손님들에의해 만들어진 코스메뉴 string과 그에 따른 횟수가 저장된다.

이걸 이용해 answer을 구하면된다.

 

 for(int i=0;i<course.size();i++)
    {    
        for(iter=m.begin();iter!=m.end();iter++)
        {
            if(iter->second>=2&&iter->first.length()==course[i]&&iter->second==maxCnt[iter->first.length()])
                answer.push_back(iter->first);
        }
}

횟수가 2이상이며, 각 메뉴의 개수에 따른 일치하는 코스 str의 길이를 찾고, 최대 횟수와 같다면 answer에 넣어주자.

 

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

 그리고 문제에서 요구한대로 정렬을 해주고 반환한다.