Algorithm
[CodeKata] 프로그래머스: 2.23(화), 메뉴 리뉴얼
ttaeng_99
2021. 2. 23. 15:09
반응형
🥋 Ooooth!! (Level 2)
orders 각 배열의 조합들 중, course 갯수들에 맞는 조합만을 모아서 반환한다는 생각으로 만들었다.
🧮 풀이
// 조합 함수
function combination(arr, num) {
let result = [];
if(num == 1) return arr.map(e => [e]);
arr.forEach((e,i,array) => {
let rest = array.slice(i+1);
let combinations = combination(rest,num-1);
let combiArr = combinations.map(x => [e, ...x])
result.push(...combiArr);
})
return result;
}
// 문제풀이 함수
function solution(orders, course) {
let answer = [];
for (let count of course) {
let courseObj = {};
for (let order of orders) {
combination(order.split(''), count).forEach((course) => {
const courseKey = course.sort().join('')
courseObj[courseKey] = courseObj[courseKey] === undefined ? 1 : courseObj[courseKey]+=1;
})
}
const courseRank = Object.entries(courseObj).filter(course => course[1] > 1).sort((a,b) => b[1]-a[1])
courseRank.filter(course => course[1] === courseRank[0][1]).forEach(course => answer.push(course[0]))
}
return answer.sort();
}1. 조합 재귀함수 활용
- combination() 함수는 재귀를 통해 조합을 구한다. 인자는 모배열(arr)과 num(조합개수) 두 가지를 받는다.
- arr 각 요소에서(forEach), 이를 제외한 나머지 배열의 조합을 구하면서 현재요소와 합쳐 조합요소를 만드는 원리이다.
2. 조합을 활용한 코스메뉴 선별
- orders, course 배열을 이중순회한다. 같은 메뉴수에서 비교되야하므로, course를 먼저 순회하며 개수에 따라 메뉴조합을 나눈다.
- courseObj 객체는 메뉴코스 조합의 개수를 누적한다. 여기의 key로 각 메뉴코스('AB', 'BCD' ...)를 적용하겠다.
- 다음으로, orders를 순회하며 각 손님의 주문내역을 count(course수) 개의 조합들을 만든다. (combination() 함수)
- 위 조합 요소들을 순회하며, 이를 string으로 join()한 courseKey key를 만들고, courseObj에 개수를 누적한다.
- 이 courseKey를 만들 때 sort() 처리가 중요하다! ('XY', 'YX' 같은 count로 들어가야하나, 주문순서에 따라 조합이 달라지므로)
- courseRank는 courseObj 객체를, 2개 이상 주문한 조합을 filter(), 그리고 개수 기준 내림차순 sort()한 배열(entries)이다.
- courseRank 0번째 요소의 개수가 최대값이 될 것이며, 이와 일치하는 모든 조합을 answer에 push()한다.
- 이렇게 모인 answer()는 메뉴코스 개수 순으로 누적되어있다. (course for문) 이를, sort() 하면 길이 상관없이 알파벳순 정렬된다.
🖇 리뷰
다른 풀이 역시, 조합을 활용해 풀었기 때문에 풀이소개보다는 순열과 조합 재귀함수에 대해 소개하려고 한다.
- 조합
function combination(arr, num) {
let result = [];
if(num == 1) return arr.map(e => [e]);
arr.forEach((e,i,array) => {
let rest = array.slice(i+1);
let combinations = combination(rest,num-1);
let combiArr = combinations.map(x => [e, ...x])
result.push(...combiArr);
})
return result;
}
combination([1,2,3,4], 3) // [[1,2,3], [1,2,4], [1,3,4], [2,3,4]]- 코드순서가 아닌, 예제의 검사순서를 따라가보자. 먼저, result는 조합들이 담길 결과배열일 것이다.
- '1'의 경우, rest는 [2,3,4]가 된다. combination([2,3,4], 2)가 재귀로 들어간다.
- '1' 내에서 '2'의 경우, rest는 [3,4]가 된다. combination([3,4], 1)가 재귀로 들어가는데, num이 1이므로 [[3],[4]]가 반환된다.
- '1' 내에서 '2'로 돌아오면, combinations는 [[3], [4]], combiArr는 [[2,3], [2,4]]가 된다. 이것이 result로 반환된다.
- '1'의 경우로 돌아오면, combinations는 [[2,3], [2,4]], combiArr는 [[1,2,3], [1,2,4]]가 된다. 이것이 result에 push() 된다.
- '1' 내에서 '3'의 경우 똑같이 반복되며, [1,3,4]가 result에 push() 될 것이다.
- '1' 내에서 '4'의 경우를 생각해보자. combination() 재귀가 발동하나, rest는 [] 빈 배열이 들어간다.
- 결국, 빈 배열을 맵핑을 한 combiArr 역시 빈 배열이며, 이를 spread operator 처리하면 result엔 아무값도 추가되지 않는다.
- 이는, arr.forEach()의 '3', '4'의 경우도 동일하다. num이 3 -> 1까지 재귀가 도는데, 그 사이에 빈배열이 형성된다.
- 결과적으론, '1'에서의 [1,2,3], [1,2,4], [1,3,4], '2'에서의 [2,3,4]만 최종 result에 담겨 반환되는 것이다.
- 순열
function combination(arr, num) {
let result = [];
if(num == 1) return arr.map(e => [e]);
arr.forEach((e,i,array) => {
let rest = [...array.slice(0,i), ...array.slice(i+1)];
let combinations = combination(rest,num-1);
let combiArr = combinations.map(x => [e, ...x])
result.push(...combiArr);
})
return result;
}
/* [
[ 1, 2, 3 ], [ 1, 2, 4 ],
[ 1, 3, 2 ], [ 1, 3, 4 ],
[ 1, 4, 2 ], [ 1, 4, 3 ],
[ 2, 1, 3 ], [ 2, 1, 4 ],
[ 2, 3, 1 ], [ 2, 3, 4 ],
[ 2, 4, 1 ], [ 2, 4, 3 ],
[ 3, 1, 2 ], [ 3, 1, 4 ],
[ 3, 2, 1 ], [ 3, 2, 4 ],
[ 3, 4, 1 ], [ 3, 4, 2 ],
[ 4, 1, 2 ], [ 4, 1, 3 ],
[ 4, 2, 1 ], [ 4, 2, 3 ],
[ 4, 3, 1 ], [ 4, 3, 2 ]
] */- 순열은 조합을 이해하면 쉽다. 보시다시피, 전체적인 로직은 유사하며 rest 배열만 조금 달라진다.
- 순열과 조합의 차이는, 순열은 중복되는(순서구분), 조합은 중복되지 않는(요소구분) 특징을 생각하면 된다.
- '2'의 경우를 생각해보자, 조합에서는 남은 요소인 ['3', '4']로 잘랐다. 하지만 순열에서는, ['1', '3', '4']로 현재요소만 뺀 배열을 다시 재귀로 돌리는 것이다.
- 즉, 순열에서는 '1'에서 ['2', '3']을 재귀했더라고, '2'에서 ['1', '3']에 대한 재귀가 다시 이루어지는 것이다.
반응형