프로그래머스 - 메뉴 리뉴얼 - C++

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

프로그래머스

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

void recur(vector<unordered_map<string,int>>& data, int len,string s,int idx,string curS)
{
    if(len == s.length()|| curS[curS.length()-1]==s[s.length()-1])
        return;
    
    for(int i=idx;i<s.length();i++)
    {
        curS+=s[i];
        data[curS.length()][curS]++;
        recur(data,curS.length(),s,i+1,curS);
        curS.pop_back();
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    vector<unordered_map<string,int>> data(11);
    
    for(int i=0;i<orders.size();i++)
    {
        sort(orders[i].begin(),orders[i].end());
        recur(data,0,orders[i],0,"");
    }
    
    for(int i=0;i<course.size();i++)
    {
        int max=-1;
        for(auto& item : data[course[i]])
        {
            if(item.second>=2&&item.second>max)
            {
                max=item.second;
            }
        }
        for(auto& item : data[course[i]])
            if(item.second==max)
                answer.push_back(item.first);
    }
    stable_sort(answer.begin(),answer.end());
    return answer;
}

이 문제는 각 손님들이 주문했던 단품메뉴들의 조합을 보고 주어진 조건에 맞는 코스메뉴 후보를 선정하는 문제이다.

 

따라서 어떻게 메뉴의 조합의 경우의 수를 만들어서 카운팅할 것인지, 그걸 어디에 저장하고 가장 많이 카운팅된 경우를 고를 것인지가 핵심이다. 

 

경우의 수를 만드는 방법은 재귀함수를 떠올렸다. 반복문을 사용하면 너무 복잡해지기 때문에( 최대 10중 for문이기 때문이다. ) 재귀함수를 사용한다. 

 

또 만든 것은 unordered_map<string,int> 의 자료구조를 만들어서 각 조합이 몇번나왔는지를 카운팅한다. 

또 이 맵을 vector에 최대 길이만큼 만들어 vector[2] 에는 메뉴수가 2인 경우의 수와 그 카운팅한 값이 들어있게 한다. 

 

vector<unordered_map<string,int>> data(11);
    
    for(int i=0;i<orders.size();i++)
    {
        sort(orders[i].begin(),orders[i].end());
        recur(data,0,orders[i],0,"");
    }

main함수이다. data라는 이름의 변수를 선언한다. 위에 설명했듯이 vector의 각 원소는 unordered_map이다. 

 

for문으로 각 orders에 대해서 모든 경우의 수를 만들기 위해 재귀함수를 호출한다. 

이 때, sort를 먼저하는 이유는 조건에 있다. 

각 메뉴는 오름차순이어야한다는 조건이다. 

 

void recur(vector<unordered_map<string,int>>& data, int len,string s,int idx,string curS)
{
    if(len == s.length()|| curS[curS.length()-1]==s[s.length()-1])
        return;
    
    for(int i=idx;i<s.length();i++)
    {
        curS+=s[i];
        data[curS.length()][curS]++;
        recur(data,curS.length(),s,i+1,curS);
        curS.pop_back();
    }
}

재귀함수이다. 

매개변수를 설명하겠다. 

data 는 참조자로 받아와 값의 변경이 main에서도 유효하게 한다. 

len은 현재 단계에서 만들어질 조합의 길이이다. 재귀함수의 종료조건을 위해 존재한다. 

s 는 원본 문자열이다. orders[i]에 해당한다.

idx 는 for문을 시작할 인덱스이다. 아래에서 설명하겠다.

curS 는 직전에 만들어진 조합이다. 

 

종료조건은 len 이 원본문자열과 같을 경우 또는 원본문자열의 가장마지막메뉴와 직전에 만든 조합의 마지막메뉴가 동일할 경우이다. 

 

조건을 이렇게 설정한 이유는 재귀함수 동작방식에 있다. 

직전에 만든 curS를 기준으로 그 다음에 메뉴를 한개씩 추가해서 data에 저장하는 방식인데 

예를 들어, s = "ABC" , curS = "A" 라고 하자. 

curS에 A를 다시 붙일 순없다. 중복메뉴는 없다했으니, 따라서 idx를 통해 어떤 메뉴부터 시작할지를 알려준다. 

또한 BA도 나올 수 없다. 오름차순으로 돼야하기 때문이다.

이렇게 만들다 curS가 AC가 되면 그 다음메뉴는 없기 때문에 종료조건에 포함된다. 

또 curS가 ABC가 되면 curS의 길이가 4가될수는 없기 때문에 종료조건에 포함이다. 

 

이런 방식으로 A를 기준으로 그 뒤에 붙을 수 있는 모든 경우를 data에 저장하고 

recur가 종료되면 curS의 마지막 메뉴를 뺀다. 

그럼 curS는 "" 에서 다음 for문을 돌며 "B" 로써 recur를 다시 시작하게 된다. 

 

for(int i=0;i<course.size();i++)
    {
        int max=-1;
        for(auto& item : data[course[i]])
        {
            if(item.second>=2&&item.second>max)
            {
                max=item.second;
            }
        }
        for(auto& item : data[course[i]])
            if(item.second==max)
                answer.push_back(item.first);
    }

재귀 함수가 종료되면 data에 각 길이에 대해서 조합이 몇개씩 나왔는지가 저장돼있다. 

course를 for문으로 돌며 각 길이에 대해서 최대값을 찾아 그에 해당하면 answer에 추가하는 코드이다. 

 

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

마지막엔 정렬을 통해 각 조합에 대해서 오름차순 정렬을 한다. 

 

아마 중복되는 메뉴가 없기에 sort를 써도 무관할 것이다. 하지만 stable_sort를 쓰는 습관을 들이려한다. 

이 차이는 

https://tpree.tistory.com/157

프로그래머스 - [3차] 파일명 정렬 - C++

이 포스트 아래쪽에 간단하게 나와있다.