[알고리즘]졸업선물 - sort 정렬, 완전탐색

문제

선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다. 학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다.
현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요. 선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는 할인에 포함되지 않습니다.

입력예제

5 28 //학생수 예산
6 6
2 2
4 3
4 5

10 3

풀이

function solution(m, product) {
        let answer = 0;
        let n = product.length;
        product.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));
        //작은 것부터 구매해야 많이 살 수 있으므로 오름차순 정렬
        for (let i = 0; i < n; i++) {
          //바깥 for문에서 미리 할인이 될 물품과 그것을 빼고 남은 나머지를 money로 정의한다.
          let money = m - (product[i][0] / 2 + product[i][1]);
          let cnt = 1; //product[i]는 구매된 물건이기 때문에 cnt를 1로 선언
          for (let j = 0; j < n; j++) {
            //안쪽 for문에서 할인 및 구매된 i번째 물품을 제외한 나머지를 남은 money와 비교한다.
            if (j !== i && product[j][0] + product[j][1] > money) break; 
            //j번째 물품가가 money보다 작다면 더 이상 구매할 수 없으므로 break.
            if (j !== i && product[j][0] + product[j][1] <= money) {
              //j번째 물품가가 money와 같거나 그보다 작다면 구매할 수 있으므로
              money -= product[j][0] + product[j][1];
              //j번째 물품가를 제외한 나머지를 다시 money에 재정의하고
              cnt++; //구매했으므로 cnt를 카운팅한다.
            }
            answer = Math.max(answer, cnt);
            //가장 높은 카운트를 비교해 answer에 재할당
          }
        }

        return answer;
      }

      let arr = [
        [6, 6],
        [2, 2],
        [4, 3],
        [4, 5],
        [10, 3],
      ];
      console.log(solution(28, arr));

arr.sort([Compare Function])

arr.sort((a, b) => (a[0] + a[1]) - (b[0] + b[1]));

• a,b 두개의 element를 파라미터로 받는 경우, 함수의 리턴 값이 0보다 작은 경우는 a가 앞으로, 0보다 클 경우는 b가 앞으로 오도록 정렬한다.
• 만약 a-b <0 이라면 a가 작으니 앞으로, a-b > 0 이라면 b가 작으니 앞으로 가는 것.
• 리턴 값 : 원본 배열인 arr이 정렬되고, 리턴 값 또한 원본 배열 arr을 가리키고 있다.