[programmers][2021카카오공채] 메뉴 리뉴얼

문제 : programmers.co.kr/learn/courses/30/lessons/72411?language=cpp

---

orders의 모든 문자열을 탐색하며 각 주문들을 먼저 오름차순 정렬 후, DFS를 돌리며 모든 조합을 구한다.

만약 구한 조합 문자열 길이가 courses에 해당된다면 해당 조합을 key값으로 하고 등장횟수를 value로 하는 map(ex, 만약 AC 조합이 2번 등장했으면 map["AC"] = 2)에 갱신한다. ( value + 1) 

 

해당 map을 다 만들었으면 탐색하면서 이번에는 조합의 길이(코스종류)를 key값, 등장횟수와 조합 리스트를 value로 가지는 map을 만든다.(ex, map[2] = [{1, "AC"}]) 이때, 등장횟수가 한 번인 경우는 메뉴가 될 수 없으므로 제외한다.

map의 value 배열을 등장횟수를 기준으로 내림차순 정렬한다. => 많이 등장할수록 초반에 나옴.

등장횟수가 같은 조합들을 모두 answer 배열에 저장한다.

answer 배열을 사전순 정렬하면 끝.

 

let, N = |orders|, M = |orders[i]|.

시간복잡도는 orders를 돌면서 모든 조합을 만드는데 O(N * (MlogM + 2^M)) + 기타 map 만드는데 드는 시간.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/2021%EC%B9%B4%EC%B9%B4%EC%98%A4%EA%B3%B5%EC%B1%84/%EB%A9%94%EB%89%B4%20%EB%A6%AC%EB%89%B4%EC%96%BC.cpp