문제 2 – 메뉴 리뉴얼

출처: 프로그래머스

주소: programmers.co.kr/learn/courses/30/lessons/72411

코딩테스트 연습 - 메뉴 리뉴얼

[문제 설명]

 1. 기존에 단품으로 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴 제공

 2. 코스요리의 메뉴를 선정 방식 결정

• 이전에 각 손님들이 주문할 때, 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 결정
• 코스요리 메뉴는 최소 2가지 이상의 단품 메뉴로 구성
• 최소 2명 이상의 손님(서로 다른 주문)으로 주무된 단품메뉴의 조합으로 결정

[예시]

 - 손님 6명(각 손님은 단품메뉴 2개 이상 주문, 단품메뉴는 A~Z로 표시)

주문한 단품메뉴

위와 같이 손님 6명이 주문을 하였을 경우, 코스요리 메뉴 구성 후보는 아래와 같다.

코스요리 후보

[문제]

=> solution 함수의 매개 변수로 orders 와 course 를 제공한다.

• 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders
• "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열  course

이런 경우, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return

 

[제한사항]

• 2 ≤orders 배열의 크기 ≤ 20
  • orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열이다.
  • 각 문자열은 알파벳 대문자로만 이루어져 있다.
  • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않는다.
• 1 ≤ course 배열의 크기 ≤ 10 
  • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있다.
  • course 배열에는 같은 값이 중복해서 들어있지 않는다.
• 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return
  • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 한다.
  • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return
  • orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어진다.

[입출력 예]

입출력 예시

[입출력 예 설명]

• 입출력 예 #2
  - AD가 3번, CD가 3번, ACD가 2번, ADE가 2번, XYZ가 2번 주문됐다.
  - 요리 5개를 주문한 손님 1명 밖에 없어서, 코스요리 후보에는 5개 요리는 추가 되지 않는다.
• 입출력 예 #3
  - WX가 2번, XY가 2번 주문됐다.
  - 3명의 손님이 모두 단품메뉴를 3개씩 주문했지만, 같은 구성으로 된 손님이 2명 이상 존재하지 않기 때문에,
    코스요리 후보에는 3개 요리는 추가 되지 않는다.
  - 또한, 단품 메뉴를 4개 이상 주문한 손님이 없기 떄문에, 코스요리 후보에도 4개 이상 후보가 존재하지 않는다.

 

[알고리즘]

 

1. 각 order마다 코스요리 후보로 가능한 조합을 계산

코스요리 후보 계산과정

 -> 아래의 코드를 이해하실 때 참고

 

2. course 개수마다 가장 많이 나온 조합들을 리스트로 저장한다.
- 두 조합이 같은 횟수만큼 나올 수 있기 때문에, 리스트로 저장

 

 

[코드]

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <utility>
 
using namespace std;
 
vector<string> solution(vector<string> orders, vector<int> course) {
    ///////////////////////////////////////////////
    // 1. 각 order마다 가능한 모든 메뉴 조합 계산 //
    ///////////////////////////////////////////////
    map<string, int> m;
    for (string &order : orders){
        // order 정렬
        sort(order.begin(), order.end());
        int n = order.size();
        // comb가 3부터 진행하는 이유
        // 3을 비트로 변환하면 00 0000 0011(order의 크기가 2 이상 10 이하 이기 때문에)
        // 따라서 최소 2개를 선택하는 가장 작은 수
        for (int comb = 3; comb < (1 << n); comb++){
            string x;
            for (int i = 0; i < n; i++){
                // comb와 (1 << i)에서 동시에 만족하는 비트가 있는 경우
                // 문자열 x에 order의 i번째 문자를 붙이기
                if (comb & (1 << i)){
                    x += order[i];
                }
            }
            // 문자열 x의 길이가 2이상인 경우
            // map에 저장
            if (x.size() > 1){
                m[x]++;
            }
        }
    }
    ///////////////////////////////////////////////////////////////////
    // 2. course 개수 별로 가장 많이 나온 조합들을 리스트로 구해준다. //
    //////////////////////////////////////////////////////////////////
    vector<string> answer;
    // course 배열의 크기가 1 이상 10 이하이다.
    // course 배열의 크기를 index로 사용하고자 tmp 배열의 크기를 11로 하였다.
    pair<int, vector<string>> tmp[11];
    for (const auto &now : m){
        string x = now.first;
        int cnt = now.second;
        // 2번 이상 나오지 않은 경우는 넘긴다.
        if (cnt <= 1){
            continue;
        }
        int len = x.size();
        // tmp의 len 인덱스의 값이 cnt 값보다 작은 경우
        // 현재 들어가는 문자열 x의 cnt가
        // 기존의 tmp[len].first보다 크면 더 많이 뽑힌 경우이기 때문에
        // 기존의 값을 버리고 현재 들어가는 문자열 x만 대입한다.
        if (tmp[len].first < cnt){
            tmp[len] = {cnt, vector<string>(1, x)};
        }
        // 기존 값(이전 최대 값)과 현재 값이 같은 경우
        else if (tmp[len].first == cnt){
            tmp[len].second.push_back(x);
        }
    }
    
    // course를 반복하면서 정답 vector에 넣기
    for (int c : course){
        for (auto x : tmp[c].second){
            answer.push_back(x);
        }
    }
 
    // 정답 vector 
    sort(answer.begin(), answer.end());
      
    
    return answer;
}

 

[느낀 점]

- map에 대한 사용법에 대해 숙지를 해야겠다.

- 조합을 계산할 때, Bit 연산자를 통해 구할 수도 있다는 것에 대해 배웠다.

 

 

[참조 사이트]

degurii.tistory.com/113