우선, 각 order들에 대한 조합의 알고리즘이 필요하여 이를 따로 구현하였다
예를 들면 [ 1, 2, 3, 4 ] 가 있을때, 3개를 골라야 한다면
결과값으로 [ [1,2,3] , [1,2,4], [2,3,4] ] 가 나오게 된다
즉, 일단 맨앞의 원소를 담고 나머지 배열 원소들을 차례대로 담은 뒤, 이에대한 개수를 만족시키면 종료되며, 중복되지 않게 담아야 한다
조합에 대한 자바스크립트 코드이다
// 배열과 조합의 수를 인자로 전달받으며
function getCombinations(arr, selectNumber){
let results = [];
// 만약, 조합의 수가 1이라면 재귀함수를 종료하게 되어있다
if (selectNumber === 1)
return arr.map((value) => [value]);
// 배열 각각에 대한 원소를 순회한다
arr.forEach((elem , index, origin)=>{
// 시작 인덱스보다 하나 더 앞에서 나머지 배열을 가져온다
const rest = origin.slice(index + 1);
// 그 나머지 배열과 조합의수 -1의 값을 다시 재귀함수로 호출
const combinations = getCombinations(rest, selectNumber - 1);
const attached = combinations.map((combination) => [elem, ...combination]);
results.push(...attached);
})
results = results.map(result =>{
result.sort();
return result.join('');
})
return results;
}
문제에 이를 적용하면 다음과 같다
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] [2]
〉 arr 로 밑의 배열을 전달하고 selectNumber는 2로 하여
[ 'A', 'C' ]
[ 'C', 'D', 'E' ]
[ 'A', 'C', 'D', 'E' ]
[ 'B', 'C', 'F', 'G' ]
[ 'A', 'B', 'C', 'F', 'G' ]
[ 'A', 'C', 'D', 'E', 'H' ]
출력된 조합 결과
[
[ 'AC' ],
[ 'CD', 'CE', 'DE' ],
[ 'AC', 'AD', 'AE', 'CD', 'CE', 'DE' ],
[ 'BC', 'BF', 'BG', 'CF', 'CG', 'FG' ],
[
'AB', 'AC', 'AF','AG', 'BC', 'BF',
'BG', 'CF', 'CG','FG'],
[
'AC', 'AD', 'AE','AH', 'CD', 'CE',
'CH', 'DE', 'DH','EH']
]
이렇게 얻어진 조합을 flat( )를 사용해 펼쳐주고, 오름차순으로 정렬하면
combinations = combinations.flat().sort();
[
'AB', 'AC', 'AC', 'AC', 'AC',
'AD', 'AD', 'AE', 'AE', 'AF',
'AG', 'AH', 'BC', 'BC', 'BF',
'BF', 'BG', 'BG', 'CD', 'CD',
'CD', 'CE', 'CE', 'CE', 'CF',
'CF', 'CG', 'CG', 'CH', 'DE',
'DE', 'DE', 'DH', 'EH', 'FG',
'FG'
]
위와 같은 값이 얻어지므로 여기서 최대로 많이 등장하는 조합의 수를 먼저 체크한후,
그 최대값을 가지는 조합을 answer에 담아주면 문제를 해결할 수 있다
최종코드는 다음과 같다👇
function solution(orders, course) {
var answer = [];
// 주문으로 들어온 string을 모두 배열로 바꿔주고, 알파벳 순으로 정렬
orders = orders.map(order=>order.split('').sort())
// 배열의 길이에 대해 오름차순으로 정렬
orders.sort((a,b) => a.length - b.length)
for(const length of course){
// 원하는 길이와 같거나 큰 배열만을 후보로 가질 수 있음
let arr = orders.filter((order)=> order.length >= length);
// 조합들을 담을 배열 초기화
let combinations = [];
// 배열의 후보가 1개라도 존재하면 실행
if(arr.length != 0){
for(const data of arr){
combinations.push(getCombinations(data, length));
}
}
// 각각의 조합들을 모두 모아 오름차순으로 정렬
combinations = combinations.flat().sort();
// 가장 많이 나오는 메뉴의 등장 횟수를 가져옴
let max = 0;
let count = 1;
for(let i = 1; i < combinations.length ; i++){
if(combinations[i-1] === combinations[i])
count++;
else
count = 1
if(max < count)
max = count;
}
// 초기화
count = 1;
// 많이 나오는 메뉴를 답안에 저장
for(let i = 1; i < combinations.length ; i++){
if(combinations[i-1] === combinations[i])
count++;
else
count = 1
if(count === max && count != 1 )
answer.push(combinations[i-1]);
}
}
// 이에대해 오름차순으로 정렬하여 문제 해결
return answer.sort();
}