[CodeKata] 프로그래머스: 2.23(화), 메뉴 리뉴얼

🥋 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]]

1. 코드순서가 아닌, 예제의 검사순서를 따라가보자. 먼저, result는 조합들이 담길 결과배열일 것이다.
2. '1'의 경우, rest는 [2,3,4]가 된다. combination([2,3,4], 2)가 재귀로 들어간다.
3. '1' 내에서 '2'의 경우, rest는 [3,4]가 된다. combination([3,4], 1)가 재귀로 들어가는데, num이 1이므로 [[3],[4]]가 반환된다.
4. '1' 내에서 '2'로 돌아오면, combinations는 [[3], [4]], combiArr는 [[2,3], [2,4]]가 된다. 이것이 result로 반환된다.
5. '1'의 경우로 돌아오면, combinations는 [[2,3], [2,4]], combiArr는 [[1,2,3], [1,2,4]]가 된다. 이것이 result에 push() 된다.
6. '1' 내에서 '3'의 경우 똑같이 반복되며, [1,3,4]가 result에 push() 될 것이다.
7. '1' 내에서 '4'의 경우를 생각해보자. combination() 재귀가 발동하나, rest는 [] 빈 배열이 들어간다.
8. 결국, 빈 배열을 맵핑을 한 combiArr 역시 빈 배열이며, 이를 spread operator 처리하면 result엔 아무값도 추가되지 않는다.
9. 이는, arr.forEach()의 '3', '4'의 경우도 동일하다. num이 3 -> 1까지 재귀가 도는데, 그 사이에 빈배열이 형성된다.
10. 결과적으론, '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 ]
] */

1. 순열은 조합을 이해하면 쉽다. 보시다시피, 전체적인 로직은 유사하며 rest 배열만 조금 달라진다.
2. 순열과 조합의 차이는, 순열은 중복되는(순서구분), 조합은 중복되지 않는(요소구분) 특징을 생각하면 된다.
3. '2'의 경우를 생각해보자, 조합에서는 남은 요소인 ['3', '4']로 잘랐다. 하지만 순열에서는, ['1', '3', '4']로 현재요소만 뺀 배열을 다시 재귀로 돌리는 것이다.
4. 즉, 순열에서는 '1'에서 ['2', '3']을 재귀했더라고, '2'에서 ['1', '3']에 대한 재귀가 다시 이루어지는 것이다.

 

- 출처: velog.io/@gytlr01/%EC%A1%B0%ED%95%A9-%EC%88%9C%EC%97%B4-%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8