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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

조합 Combination

맵 Map

---

 

 

코드

 

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

vector<string> answer;	// 결과를 저장할 벡터
map<string, int> myMap; // 각 메뉴 조합의 주문 횟수를 저장할 맵
int ch[10]; 			// 조합 생성 시, 해당 인덱스의 문자가 사용되었는지 확인하는 배열

// 주어진 문자열에서 select 개수만큼의 문자를 선택하는 모든 조합을 생성하는 함수
void Combination(string ord, string str, int idx, int select)
{
    // select 개수만큼의 문자를 선택한 경우
	if(str.size() == select){
        sort(str.begin(), str.end()); 	// 생성된 조합을 사전 순으로 정렬 (게시글 아래 추가설명 참조)
        myMap[str]++; 					// 해당 조합의 주문 횟수를 증가
        return;
	}

    // ord 문자열의 idx 위치부터 시작하여 조합을 생성
    for(int i = idx; i<ord.size(); i++)
    {
        if (ch[i] == 0) // 해당 위치의 문자가 아직 선택되지 않은 경우
        {
            ch[i] = 1; // 선택 표시
            Combination(ord, str + ord[i], i + 1, select); // 선택한 문자를 str에 추가하고, 다음 위치부터 조합을 생성
            ch[i] = 0; // 선택 해제
        }
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
        
    for (int i = 0; i < orders.size(); i++) { // 모든 주문에 대하여
        for (int j = 0; j < course.size(); j++) { // course에 포함된 개수만큼의 메뉴를 선택하는 조합을 생성
            Combination(orders[i], "", 0, course[j]);
        }
    }

    for (int i = 0; i < course.size(); i++)  // course에 포함된 모든 메뉴 개수에 대하여
    {
        int max_value = 0; // 가장 많이 주문된 횟수를 저장할 변수
        
        for (const auto& it : myMap) { // 모든 메뉴 조합에 대하여
            // 해당 메뉴 조합의 길이가 현재 course[i]와 같고, 주문 횟수가 1 이상이며, 주문 횟수가 현재 max_value보다 크다면
            if (it.first.size() == course[i] && it.second > 1 && it.second > max_value) {
                max_value = it.second; // max_value 갱신
            }
        }
       
        for (const auto& it : myMap) {  // 모든 메뉴 조합에 대하여
            // 해당 메뉴 조합의 길이가 현재 course[i]와 같고, 주문 횟수가 max_value와 같다면
            if (it.first.size() == course[i] && it.second == max_value) {
                answer.push_back(it.first);
            }
        }
    }

    sort(answer.begin(), answer.end()); // answer 벡터를 사전 순으로 정렬

    return answer; 
}

 

 

---

 

주의할점

 

중간에 sort(str.begin(), str.end()); 를 넣어야 하는 이유

 

sort(str.begin(), str.end());는 메뉴 조합을 생성할 때 각 메뉴를 사전 순서로 정렬하는 역할을 한다. 이 과정이 필요한 이유는, 조합을 생성하는 과정에서 동일한 메뉴 조합이지만 메뉴의 순서가 다른 경우를 피하기 위함이다.

예를 들어, "AB"와 "BA"는 서로 다른 문자열이지만, 메뉴 조합이라는 관점에서 보면 두 조합은 동일하다. 따라서 메뉴 조합을 생성하면서 메뉴를 사전 순으로 정렬하면, 동일한 메뉴 조합이라도 항상 같은 문자열로 표현되어 myMap에서 동일한 키로 취급할 수 있다.

따라서 sort(str.begin(), str.end());는 동일한 메뉴 조합에 대해 동일한 문자열을 생성하기 위한 필수적인 과정이다. 이 과정이 없다면, 동일한 메뉴 조합이라도 메뉴의 순서에 따라 다른 키로 취급되어, 각각의 메뉴 조합의 주문 횟수를 정확히 계산할 수 없게 된다.

마지막의 sort(answer.begin(), answer.end();는 결과적으로 선택된 메뉴 조합들을 사전 순으로 정렬하기 위한 과정이다. sort(str.begin(), str.end());정렬과는 무관하다.

 

 

---