[JS알고리즘] 졸업선물

선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다.

학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라

고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다.

현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요.

선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는

할인에 포함되지 않습니다.

function solution(m, product){
  let answer=0;
  let n=product.length;	//학생수
  product.sort((a, b)=>(a[0]+a[1])-(b[0]+b[1])); //총비용으로 sort 해야함
  for(let i=0; i<n; i++){	// for of 로 돌면 안됨. 상품정보를 하나씩 돌면서 할인받는다고 가정해봄
    let money=m-(product[i][0]/2+product[i][1]);	//남은금액
    let cnt=1;
    for(let j=0; j<n; j++){
      if(j!==i && (product[j][0]+product[j][1])>money) break;
      if(j!==i && (product[j][0]+product[j][1])<=money){
        money-=(product[j][0]+product[j][1]);
        cnt++;
      }
    }
    answer=Math.max(answer, cnt);
  }  
  return answer;
}

let arr=[[6, 6], [2, 2], [4, 3], [4, 5], [10, 3]];
console.log(solution(28, arr));	//예산, 상품정보

모든 상품이 한번씩은 다 할인받았다는 가정으로 계산해봐야 한다 ( 이 생각을 해내는게 관건 )
answer는 최대 갯수이므로 0으로 세팅한다
` let money=m-(product[i][0]/2+product[i][1]);` => 할인받은 금액을 전체금액에서 뺀 금액 = 남은금액
상품의 가격(product[i][0])과 상품의 배송료(product[i][1])는 [0]과 [1]에 들어있다
cnt 변수를 만들고 몇개를 살 수 있는지 카운트해준다
j!==i i는 구매하면 안됨 (이미 할인을 받았기 때문에). 그래서 index가 필요하기 떄문에 for도 index for가 필요함
(product[j][0]+product[j][1])<=money => 남은 금액보다 상품가격과 배송료의 합이 작아야 구매할 수 있다.
money-=(product[j][0]+product[j][1]); => 남은 예산에서 상품가격+배송료를 빼주고 cnt를 ++해준다
if(j!==i && (product[j][0]+product[j][1])>money) break; => 남은금액이 부족하면 break해준다 (상품갯수가 많으면 헛바퀴 도는것이기 떄문에 중간에 끊어주어야 함)
answer=Math.max(answer, cnt); 둘중에 더 큰 값으로 answer를 바꿔준다

이것도 전형적인 브루트포스 문제.

모든 경우의 수를 다 고려해야하는데 어떤 모든 경우의 수를 생각해내는지가 관건이다

inflearn 자바스크립트 알고리즘 강의 내용 =)

Share this post