[스위프트 알고리즘] 프로그래머스: 메뉴 리뉴얼

문제

https://programmers.co.kr/learn/courses/30/lessons/72411?language=swift 

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

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.

단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

 

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

손님 번호주문한 단품메뉴 조합

1번 손님	A, B, C, F, G
2번 손님	A, C
3번 손님	C, D, E
4번 손님	A, C, D, E
5번 손님	B, C, F, G
6번 손님	A, C, D, E, H

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류메뉴 구성설명

요리 2개 코스	A, C	1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스	C, D, E	3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스	B, C, F, G	1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스	A, C, D, E	4번, 6번 손님으로부터 총 2번 주문됐습니다.

---

[문제]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

풀이

문제를 읽고 조합으로 푸는 것 말고는 방법이 없지 않을까? 라는 생각을 했습니다. 실제로 주문의 최대 개수는 20개, 한 주문안에 포함되는 메뉴의 최대 개수는 10개이기 때문에 시간초과 없이 충분히 가능해보였습니다. 보통 1초에 1억번의 연산이 가능하기 때문에 10! * 20을 최대로 잡으면 조합 계산만 1초안에 가능하다고 생각하고 조합으로 풀이를 시작했습니다. 

 

먼저 각 주문에 대해 course 배열에 들어있는 값으로 만들 수 있는 조합을 찾아줍니다. 예를들어,

 

["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2,3,5]

 

의 경우에는 첫번째 주문인 "ABCDE"에 대해 2개, 3개, 5개를 뽑아 만들 수 있는 조합을 만듭니다. 이렇게 얻은 조합은 하나의 배열에 넣어 다음과 같이 표현할 수 있습니다.

 

2개 뽑을 때: ["AB", "AC", "AD", "AE", "BC", "BD", "BE", "CD", "CE", "DE"]

3개 뽑을 때: ["ABC", "ABD", "ABE", "ACD", "ACE", "ADE", "BCD", "BCE", "BDE", "CDE"]

5개 뽑을 때: ["ABCDE"]

 

이번 주문에 대한 전체 가능한 조합:

["AB", "AC", "AD", "AE", "BC", "BD", "BE", "CD", "CE", "DE", "ABC", "ABD", "ABE", "ACD", "ACE", "ADE", "BCD", "BCE", "BDE", "CDE", "ABCDE"]

 

이렇게 모든 주문에 대해 course 의 값들에 대한 조합을 만들어 저장하면, 각 주문에서 얻을 수 있는 조합들을 모아 배열로 만들 수 있습니다. 이제 각 조합들이 몇번씩 등장했는지 알아내야합니다. 저는 이를 위해서 [String : Int] 타입의 딕셔너리를 선언하여 조합과 그 개수를 저장하도록 했습니다. course의 들어있는 값들을 하나씩 뽑아가며 2개씩 뽑을 때, 3개씩 뽑을 때, 5개씩 뽑을 때에 대한 개수를 세어주면 다음과 같은 형태로 개수를 얻게됩니다.

 

["AE": 2, "AB": 2, "CD": 3, "BE": 1, "DE": 2, "YZ": 2, "XY": 2, "XZ": 2, "BC": 1, "BD": 1, "AD": 3, "CE": 1, "AC": 2]

 

이제 가장 큰 등장횟수 값을 구하고, 해당 값을 value로 가지는 key를 모두 찾아 정답 배열에 넣는 과정을 각 길이의 조합들에 대해 반복하면 정답을 얻게됩니다.

코드