[ 프로그래머스 메뉴 리뉴얼 (Lv2) ] (C++)

프로그래머스의 메뉴 리뉴얼(Lv2) 문제이다.

[ 문제풀이 ]

추가하고 싶은 코스요리의 단품메뉴들의 갯수가 담긴 정보를 통해서, 새로 추가하게 될 코스요리의 메뉴 구성을 구해야 하는 문제이다.

문제를 단계별로 나눠서 진행해 보도록 하자.

#1. 코스요리의 조합에 들어갈 수 없는 단품메뉴

가장 먼저, 코스요리에 들어갈 수 있는 단품메뉴와 그럴 수 없는 단품메뉴를 한번 나눠보자.

과연 어떤 메뉴가 코스요리의 구성에 속할 수 없게 될까 ??

문제에 보면 이런 문구가 있다. "최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다" 그리고 다음과 같은 메뉴들을 손님들이 주문했다고 가정해보자.

1번손님 = [ A , B ]

2번손님 = [ A , B , C ]

3번손님 = [ C , D ]

4번손님 = [ D , E , F ]

5번손님 = [ E , F , G ]

위의 상황에서 한번이라도 주문된 모든 단품메뉴들을 적어보면 [ A , B , C , D , E , F , G ] 가 있다.

그런데 이 메뉴들 중, 코스요리를 만들 때 절대로 포함될 수 없는 단품메뉴는 뭐가 있을까 ??

바로 'G'이다. 왜냐하면, 코스요리에 들어가는 단품메뉴들은 최소 2명 이상의 손님으로부터 주문된 단품메뉴만 사용한다고

하였기 때문에, 5번손님 1명한테만 주문이 된 'G'는 코스요리에 들어갈 수 없게 된다.

반대로 A, B, C, D, E, F는 코스요리에 들어갈 수 있는 후보는 될 수 있음을 의미한다.

본인은 가장 처음으로 이 과정을 진행해 주었다. 자료구조 map을 이용해서 각 메뉴가 주문된 횟수를 판단해서 2번 이상 주문된 단품메뉴들에 대해서만 따로 저장을 해 주었다.

#2. 갯수에 따른 조합 구현하기

두 번째 과정이자 어떻게 보면 최종 과정이다. 우리는 코스요리에 들어갈 단품메뉴의 갯수를 매개변수(course)로 받게 된다.

그리고 #1에서 구해놓은 "코스요리에 들어가는 단품메뉴"들을 조합을 이용해서 구현해주었다.

왜 조합일까 ?? 예를 들어서 2개의 단품메뉴가 들어가는 코스요리를 만든다고 가정을 해보자.

이 때, 단품메뉴 [ A , B ] 를 이용해서 코스요리를 만드는 것과 , [ B , A ] 를 이용해서 코스요리를 만드는 것의 차이가

있을까 ?? 아니다. 동일한 코스요리일 것이다. 즉 ! 순서에 영향을 미치지 않기 때문에 순열이 아닌 조합을 이용해서 구현해 주었다. 아직 조합에 대해서 모른다면 아래의 글을 읽고 오도록 하자.

[ 조합 알아보기(Click) ]

그럼 위의 글을 읽었다면, 지금부터 조합을 재귀를 통해서 구현해볼 것인데, 먼저 필요한 매개변수가 무엇이 있는지부터 알아보자. (제 코드에서는 필요한 매개변수들이 조금 많습니다.)

가장 먼저, 조합을 구현할 때 필요한 "시작점을 결정하는 변수" 와 "현재 몇 개를 뽑았는지를 저장해놓는 변수" 그리고 "몇 개를 뽑아야 하는지를 저장해놓는 변수" 이렇게 기본적으로 3개가 필요할 것이다.

여기서 "몇 개를 뽑아야 하는지를 저장해놓는 변수" 에는 course의 값들이 들어가게 될 것이다.

이 외에 어떤 변수들이 더 필요할까 ?? 본인은 다음과 같은 변수들을 매개변수로 설정해 주었다.

1. 가장 많이 주문된 횟수

가장 많이 함께 주문된 메뉴 구성을 코스요리의 메뉴들로 만들 것이라고 했다. 즉 ! 조합을 통해서 특정 재료들을 뽑았다면,

해당 재료들이 몇 번 주문되었는지를 계산해 주어야 한다. 이 계산을 통해서, "가장 많이 주문된 횟수"를 저장해놓고, 이 값보다 더 많이 주문된 재료들이 있는지 없는지를 판단하면서 코스요리의 메뉴들을 선정해 주어야 한다.

2. 가장 많이 주문된 횟수를 가진 단품메뉴들

1번에서 가장 많이 주문된 횟수를 저장했다면, 이 가장 많이 주문된 단품메뉴들이 어떤 메뉴들이였는지 또한 당연히 알고 있어야 할 것이다. 왜냐하면 이 메뉴들을 통해서 코스요리를 만들 것이기 때문이다.

3. 최종 선정된 단품메뉴들을 저장하기 위한 변수

1, 2번을 통해서 어떤 단품메뉴들을 코스요리에 사용할 건지 알았다면, 이 메뉴들을 최종적으로 저장해 주기 위한 변수이다.

void DFS(int Idx, int Cnt, int Target_Cnt, int &Max_Cnt, vector<bool> &Select, 
         vector<char> &Select_Type, vector<char> Cnd, vector<string> orders, vector<string> &Res)
 

본인이 선언한 DFS 함수이다. 딱 봐도 매개변수가 굉장히 많다.

1. Idx = 조합에서 "시작점을 결정하는 변수"

2. Cnt = 조합에서 "현재 몇 개를 뽑았는지 결정하는 변수"

3. Target_Cnt = 조합에서 "몇 개를 뽑아야 하는지를 알려주는 변수"

- 이 Target_Cnt라는 변수에 course값이 들어가는 것이다.

4. Max_Cnt

- 이 변수가 위에서 설명한 1번내용인 "가장 많이 주문된 횟수"를 저장하기 위한 변수이다.

5. Select

- 조합에서 "현재 x번째 값을 뽑았는지 안뽑았는지"를 판단하기 위해서 사용되는 변수이다.

  위의 조합 글에서는 bool Select[] 라는 1차원 배열을 전역변수로 만들어서 사용했지만, 이 문제에서는 vector를 이용했고

  전역변수가 아닌 매개변수로 사용해서 구현하였다. (무슨 방법을 사용하든 상관 없습니다.)

6. Select_Type

- x번째 값을 뽑았다면, 이 'x'라는 값을 저장하기 위한 변수이다.

  만약, Target_Cnt개 만큼 뽑았다면 우리는 이 vector에 저장되어 있는 재료들을 통해서 우리가 뽑은 재료가 무엇인지

  판단할 수 있다.

7. Cnd

- 이 변수는 #1의 과정에서 구해놓은 "우리가 코스요리의 메뉴로 삼을 수 있는 단품메뉴들 리스트" 가 저장되어 있는 변수이다.

  우리는 이 리스트에서 몇 개의 메뉴들을 뽑아야 하기 때문에 매개변수로 가져와서 이 정보를 호라용해 주었다.

8. Orders

- 문제의 매개변수로 주어지는 Orders를 DFS함수 내에서도 사용해야 하므로 호출해준 것이다.

9. Res

- 위에서 설명한 3번 내용인 "최종적으로 선정된 단품메뉴들" 을 저장하기 위한 변수이다.

그렇다면 만약 뽑고싶은 만큼 단품메뉴의 수만큼 뽑았다면, 어떤 계산을 진행해주면 될까 ??

해야할 일들을 적어본다면 다음과 같이 적을 수 있을 것이다.

1. 현재 뽑은 단품 메뉴 세트가 몇 번 주문되었는지 판단하기

2. 1번 과정을 통해서 판단한 주문된 횟수와 기존에 설정되어 있는 "가장 많이 주문된 횟수"와 비교하기

3. 2번 과정을 통해서 비교한 주문 횟수가 가장 많이 주문된 횟수와 같다면 ?

   - 최종적으로 선정된 코스요리 리스트에 추가하기

3-2) 2번 과정을 통해서 비교한 주문 횟수가 장 많이 주문된 횟수보다 더 크다면 ?

   - 기존에 가장 많이 주문된 코스요리 리스트들은 더 이상 의미가 없어지므로 모두 삭제 후, 이 코스요리만 넣어주기

이런식으로 적어볼 수 있다. 코드로 확인하면 다음과 같다.

if (Cnt == Target_Cnt)
{
    int Result_Cnt = 0;
    string Result_Type = "";
    for (int i = 0; i < Select_Type.size(); i++) Result_Type += Select_Type[i];
    for (int i = 0; i < orders.size(); i++)
    {
        bool Flag = true;
        for (int j = 0; j < Select_Type.size(); j++)
        {
            if (orders[i].find(Select_Type[j]) == -1)
            {
                Flag = false;
                break;
            }
        }
        if (Flag == true) Result_Cnt++;
    }
    
    if (Result_Cnt < 2 || Result_Cnt < Max_Cnt) return;
    if (Result_Cnt == Max_Cnt) Res.push_back(Result_Type);
    else if (Result_Cnt > Max_Cnt)
    {
        Max_Cnt = Result_Cnt;
        Res.clear();
        Res.push_back(Result_Type);
    }
    return;
}

line6)에서 보면 각 손님별로 시켜먹은 단품 메뉴들을 탐색하면서 line9)에서 "현재 내가 고른 단품메뉴들"이

몇 번 주문되었는지 확인하기 위해서 line11)에서 손님별로 몇 번 주문되었는지 확인을 한다.

예를 들어서 구체적으로 알아보자.

1번 손님 = [ A , B ]

2번 손님 = [ A , B , C ]

3번 손님 = [ B , C ]

이렇게 주문했다고 가정했고 현재 내가 뽑은 코스요리에 들어갈 단품메뉴 리스트가 [ "AB" ] 라고 가정해보자.

즉, A와 B를 모두 주문한 손님이 총 몇명인지를 구해야 하는 상황이다.

그럼 1번 2번 3번 손님에 대해서 모두 탐색을 하기 위한 반복문이 line6)의 반복문이고, 각 손님들이 주문한 단품메뉴 리스트들을 확인하기 위한 반복문이 line9)의 반복문이다.

line11)에서는 "A"와 "B"모두 주문 했는지 판단을 하기 위한 변수이다.

1번손님과 2번손님은 line11)의 조건문에 들어가지 않을 것이다. 왜냐하면 A와 B모두 주문한 손님이기 떄문이다.

하지만, 3번 손님은 'A'를 주문하지 않았기 때문에 이 조건문에 들어가게 될 것이다.

line20)에서는 "2번 미만으로 주문된 단품메뉴들 이거나 기존에 설정된 가장 많이 주문된 횟수보다 더 적다면" 별다른

연산 없이 그대로 return 시켜주는 모습이다.

line21과 line22는 위에서 설명한 3번 과정을 나타낸 것이다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
 
void DFS(int Idx, int Cnt, int Target_Cnt, int &Max_Cnt, vector<bool> &Select, 
          vector<char> &Select_Type, vector<char> Cnd, vector<string> orders, vector<string> &Res)
{
    if (Cnt == Target_Cnt)
    {
        int Result_Cnt = 0;
        string Result_Type = "";
        for (int i = 0; i < Select_Type.size(); i++) Result_Type += Select_Type[i];
        for (int i = 0; i < orders.size(); i++)
        {
            bool Flag = true;
            for (int j = 0; j < Select_Type.size(); j++)
            {
                if (orders[i].find(Select_Type[j]) == -1)
                {
                    Flag = false;
                    break;
                }
            }
            if (Flag == true) Result_Cnt++;
        }
        
        if (Result_Cnt < 2 || Result_Cnt < Max_Cnt) return;
        if (Result_Cnt == Max_Cnt) Res.push_back(Result_Type);
        else if (Result_Cnt > Max_Cnt)
        {
            Max_Cnt = Result_Cnt;
            Res.clear();
            Res.push_back(Result_Type);
        }
        return;
    }
 
    for (int i = Idx; i < Cnd.size(); i++)
    {
        if (Select[Cnd[i] - 'A'] == true) continue;
        Select[Cnd[i] - 'A'] = true;
        Select_Type.push_back(Cnd[i]);
        DFS(i, Cnt + 1, Target_Cnt, Max_Cnt, Select, Select_Type, Cnd, orders, Res);
        Select_Type.pop_back();
        Select[Cnd[i] - 'A'] = false;
    }
}
 
vector<string> solution(vector<string> orders, vector<int> course) 
{
    vector<string> answer;
    vector<char> Candidate;
    map<char, int> Visit;
    for (int i = 0; i < orders.size(); i++)
    {
        for (int j = 0; j < orders[i].length(); j++)
        {
            char C = orders[i][j];
            if (Visit[C] == 0) Visit[C]++;
            else if (Visit[C] == 1)
            {
                Visit[C]++;
                Candidate.push_back(C);
            }
        }
    }
    sort(Candidate.begin(), Candidate.end());
 
    for (int i = 0; i < course.size(); i++)
    {
        int Max_Cnt = 0;
        vector<bool> Select(27, false);
        vector<char> Select_Type;
        vector<string> Result;
        DFS(0, 0, course[i], Max_Cnt, Select, Select_Type, Candidate, orders, Result);
        for (int j = 0; j < Result.size(); j++) answer.push_back(Result[j]);
    }
    sort(answer.begin(), answer.end());
    return answer;
}