[C++] Programmers Lv. 2 "메뉴 리뉴얼"

🔵 문제 링크

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

프로그래머스

 

🔵 접근 방식

orders의 배열 길이는 최대 20, 그 문자열의 최대 길이가 10으로 매우 작으므로, 문자열의 모든 조합을 구하여 풀어 보았다.

• 코스 요리의 모든 조합을 만들어 hash에 등록, value의 값은 그 조합을 주문한 횟수
• orders를 돌면서 hash에 데이터 갱신
• 이후 조건에 맞는 key(코스 요리 조합)들만 뽑아서 answer에 push 후 정렬한다.

 

💡 Point : 문자열 모든 조합 찾기

🔷 비트 마스크

// 문자열 조합 생성 후 hash 등록
void generateCombinations(const string& str)
{
    string sortedStr = str;

    // 문자열 조합을 만들기 위한 정렬
    sort(sortedStr.begin(), sortedStr.end());

    int n = sortedStr.length();

    // 0부터 2^n - 1까지 순회하며 비트 마스크로 조합 생성
    // 몇 번째 비트가 켜졌는지에 따라 문자 껐다 켜기 -> 조합 생성 가능

    // i = 0은 아무 문자도 선택 안 한 공집합을 뜻하므로 제외하고 시작
    for (int i = 1; i < (1 << n); i++)
    {
        string comb = "";
        for (int k = 0; k < n; k++)
        {
            // k 번째 비트가 켜져 있으면 k번째 문자를 선택
            // i라는 숫자의 k 번째 비트가 1인지 0인지 확인하는 방법.
            if ((i >> k) & 1)
                comb += sortedStr[k];
        }
        if(comb.length() >= 2)
            orderTable[comb]++;
    }
}

 

문자열의 자릿수가 n이라 할 때, 2^n - 1까지 순회하며 문자의 조합을 찾는 코드이다.

무슨 말이냐면, 어떤 집합의 크기가 n이라 할 때 그 집합의 부분 집합 개수를 구하듯이 푸는 것이다.

예를 들어 문자열이 "abc"라 할 때, 문자의 조합은 [ a 사용 여부 ] [ b 사용 여부 ] [ c 사용 여부 ] 로 표현할 수 있다.

[ true ] [ false ] [ true ]이면, 문자열은 "ac"가 되는 것이다. 마찬가지로 [ false ][ true ][ true ]이면 문자열은 "bc"가 된다.

참고로 [ false ] [ false ] [ fasle ]는 공집합이므로 문자열은 ""이 된다. 위 코드에서는 이 조건을 제외하였다.

이를 효율적으로 구현하기 위해 비트 마스크 방식을 사용한 것이다.

 

🔷 재귀 함수

void comb(string src, string dst, int depth)
{
    if (dst.size() == depth) orderTable[dst]++;
    else
    {
        for (int i = 0; i < src.size(); i++)
            comb(src.substr(i + 1), dst + src[i], depth);
    }
}

 

위 비트 마스크 방식보다 쉽게 떠올릴 수 있는 방식이다.

재귀 함수를 이용하여 필요한 depth(length)만큼의 문자열 조합을 얻을 수 있다.

src.substr(i + 1)를 통해 현재 선택한 문자를 제외한 나머지 문자를 넘겨 주어 중복을 피한다.

 

참고로 위 두 방법 모두 문자열 조합을 찾기 전에 문자열을 정렬 시켜야 한다.

왜냐하면 "BAC", "CAB"라는 문자열이 있다고 가정했을 때, 각 문자의 조합 "AB", "BA"를 서로 다른 키로 인식할 수 있기 때문이다.

 

🔵 전체 코드

비트 마스크 방법으로 풀이하였다.

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

// 코스 요리는 최소 2가지 이상의 단품 메뉴로 구성
// 최소 2명 이상의 손님으로부터 주문되어야 함

// orders : 손님들이 주문한 단품메뉴들 
// course : 코스요리 단품 개수

unordered_map<string, int> orderTable;

// 문자열 조합 생성 후 hash 등록
void generateCombinations(const string& str)
{
    string sortedStr = str;

    // 문자열 조합을 만들기 위한 정렬
    sort(sortedStr.begin(), sortedStr.end());

    int n = sortedStr.length();

    // 0부터 2^n - 1까지 순회하며 비트 마스크로 조합 생성
    // 몇 번째 비트가 켜졌는지에 따라 문자 껐다 켜기 -> 조합 생성 가능

    // i = 0은 아무 문자도 선택 안 한 공집합을 뜻하므로 제외하고 시작
    for (int i = 1; i < (1 << n); i++)
    {
        string comb = "";
        for (int k = 0; k < n; k++)
        {
            // k 번째 비트가 켜져 있으면 k번째 문자를 선택
            // i라는 숫자의 k 번째 비트가 1인지 0인지 확인하는 방법.
            if ((i >> k) & 1)
                comb += sortedStr[k];
        }
        if(comb.length() >= 2)
            orderTable[comb]++;
    }
}

// 수가 작으므로 모든 조합을 생각해 본다?
vector<string> solution(vector<string> orders, vector<int> course) 
{
    for (int i = 0; i < orders.size(); i++)
    {
        generateCombinations(orders[i]);   
    }

    vector<string> answer;

    // 각 코스 길이(course[i])별로 처리
    for (int len : course) 
    {
        int maxCount = 1; 

        // 해당 길이(len)를 가진 조합들 중 최대 주문 횟수를 찾는다.
        for (const auto& pair : orderTable)
        {
            if (pair.first.length() == len)
            {
                maxCount = max(maxCount, pair.second);
            }
        }

        // 만약 maxCount가 2 미만이면, 해당 길이의 코스 요리는 유효하지 않으므로 건너뛴다.
        if (maxCount < 2)
            continue;

        // 해당 길이(len)를 가지면서 maxCount와 동일한 주문 횟수를 가진 조합들을 answer에 추가한다.
        for (const auto& pair : orderTable)
        {
            if (pair.first.length() == len && pair.second == maxCount)
            {
                answer.push_back(pair.first);
            }
        }
    }

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

    return answer;
}