졸업 선물
문제 설명
선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다. 학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다. 현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요.
선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는 할인에 포함되지 않습니다.
▣ 입력설명
첫 번째 줄에 반 학생수 N(1<=N<=1000)과 예산 M(1<=M<=100,000,000)이 주어진다. 두 번째 줄부터 N줄에 걸쳐 각 학생들이 받고 싶은 상품의 가격과 배송비가 입력됩니다. 상품가격과 배송비는 각각 100,000을 넘지 않습니다.
상품가격은 짝수로만 입력됩니다.
▣ 출력설명
첫 번째 줄에 선생님이 현재 예산으로 선물할 수 있는 최대 학생수를 출력합니다. 선생님 최소한 1개 이상의 상품을 살 수 있는 예산을 가지고 있습니다.
▣ 입출력 예
| arr | return |
|---|---|
| 5 28 / [[6,6], [2,2], [4,3], [4,5], [10, 3]] | 4 |
(2, 2), (4, 3), (4, 5)와 (10, 3)를 할인받아 (5, 3)에 사면 비용이
4+7+9+8=28입니다.
풀이
1차 시도
const maxGift = (예산, arr) => {
let maxNum = 0;
const sortedArr = [...arr];
sortedArr.sort((a, b) => {
const sumA = a.reduce((acc, val) => acc + val, 0);
const sumB = b.reduce((acc, val) => acc + val, 0);
return sumA - sumB;
});
for (let i = 0; i < arr.length; i++) {
let 남은예산 = 예산 - (sortedArr[i][0] / 2 + sortedArr[i][1]);
let num = 0;
for (let j = 0; j < sortedArr.length; j++) {
if (남은예산 >= sortedArr[j][0] + sortedArr[j][1]) {
남은예산 -= sortedArr[j][0] + sortedArr[j][1];
num++;
}
}
maxNum = Math.max(maxNum, num);
}
return maxNum;
};
let arr = [
[6, 6],
[2, 2],
[4, 3],
[4, 5],
[10, 3],
];
console.log(maxGift(28, arr));❓ 문제점
-
num 변수를 적절히 증가시키기 위해, 이미 할인 적용된 선물을 구매한 경우 num을 1로 초기화해야 한다.
👉 즉 첫번째 for문에서 이미i번째의 선물을 할인가에 구매한다고 가정하였으므로 num을 1로 적용한 상태에서 탐색을 시작하는 것이 맞다. -
이미 할인 적용된 선물은 제외해야한다.
👉 첫 번째 for문에서의 i는 이중for문의 j와 비교해서 같은 값이라면 이미 할인적용된 선물과 같으므로 건너뛰어야한다.😤
수정 코드
const maxGift = (예산, arr) => {
let maxNum = 0;
const sortedArr = [...arr];
sortedArr.sort((a, b) => {
const sumA = a.reduce((acc, val) => acc + val, 0);
const sumB = b.reduce((acc, val) => acc + val, 0);
return sumA - sumB;
});
for (let i = 0; i < arr.length; i++) {
let 남은예산 = 예산 - (sortedArr[i][0] / 2 + sortedArr[i][1]);
let num = 1; // 할인 적용된 선물을 구매한 경우 1로 초기화 ⭐️
for (let j = 0; j < sortedArr.length; j++) {
// 할인 적용된 선물 제외 ⭐️
if (i !== j) {
if (남은예산 >= sortedArr[j][0] + sortedArr[j][1]) {
남은예산 -= sortedArr[j][0] + sortedArr[j][1];
num++;
}
}
}
maxNum = Math.max(maxNum, num);
}
return maxNum;
};
let arr = [
[6, 6],
[2, 2],
[4, 3],
[4, 5],
[10, 3],
];
console.log(maxGift(28, arr));개선하기
const sortedArr = [...arr];
sortedArr.sort((a, b) => {
const sumA = a.reduce((acc, val) => acc + val, 0);
const sumB = b.reduce((acc, val) => acc + val, 0);
return sumA - sumB;
});reduce 함수대신 직접 더하는 방식
👇👇👇
const sortedArr = [...arr];
sortedArr.sort((a, b) => {
const sumA = a[0] + a[1]; // reduce 대신 직접 더하기
const sumB = b[0] + b[1];
return sumA - sumB;
});✍️ 아래 코드로의 개선점 🤨
(1) 효율성
reduce 함수는 각 배열 요소에 대해 콜백 함수를 실행한다. 이 경우 배열 요소가 단순 두 개(가격, 배송비)뿐이므로, reduce의 처리는 과하다. 이럴땐 직접 두 요소를 더하는 것이 더 효율적!🧐
📌reduce 함수는 보통 배열 요소가 더 많고 복잡한 축적 연산을 수행할 때 유용하다
(2) 코드의 명확성
직접 더하는 방식이 여기서는 코드의 의도를 더 명확하게 할 수 있다. a[0] + a[1] 과 b[0] + b[1] 는 각각 배열의 첫 번째 요소인 '가격'과 두 번재 요소인 '배송비'를 더한다는 것을 분명히 보여줄 수 있다.
✍️ solution
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++){
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));