✏️ 문제 설명
선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다.
학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라 고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다.
현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요. 선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는 할인에 포함되지 않습니다.
✏️ 입력 설명
첫 번째 줄에 반 학생수 N(1<=N<=1000)과 예산 M(1<=M<=100,000,000)이 주어진다. 두 번째 줄부터 N줄에 걸쳐 각 학생들이 받고 싶은 상품의 가격과 배송비가 입력됩니다. 상품가격과 배송비는 각각 100,000을 넘지 않습니다. 상품가격은 짝수로만 입력됩니다.
✏️ 입출력 예제
입력
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입니다.
가격 + 배송비를 작은 순서대로 정렬해서 m보다 작을 때까지 사도록 하는 게 핵심이라고 생각! 여기까지 떠올리는 건 쉬웠지만 쿠폰 적용을 어떻게 시키고 어떻게 정렬하는 게 좋을지 생각하다가 한참 헤맸다.
쿠폰을 모든 상품에 적용해봐야 한다는 점에서 완전 탐색 유형으로 분류되는 문제였음!
🔍 제출한 풀이
function solution(m, product) {
let result = 0;
for (let i = 0; i < product.length; i++) {
let totalCost = 0;
let count = 0;
// i번째 상품 할인
product[i][0] = product[i][0] * 0.5;
// 할인한 이후 상품 가격 + 배송비로 정렬
const sortedArray = product
.map((value) => value.reduce((acc, cur) => acc + cur))
.sort((a, b) => a - b);
// 예산 내에서 상품 구매
for (let j = 0; j < product.length; j++) {
// j번째 상품을 예산 안에서 구매할 수 있다면
if ((totalCost + sortedArray[j]) <= m) {
// 총 비용에 상품값을 더하고 count 올려주기
totalCost += sortedArray[j];
count++;
} else {
// 구매할 수 없다면 반복문 탈출 후 다음 상품 할인 받기
// 할인 받은 상품 가격 원래대로 돌리기
product[i][0] = product[i][0] * 2;
break;
}
result = Math.max(count, result);
}
}
return result;
}강의 커뮤니티에 있던 다른 분 풀이를 조금 참고했는데 가격과 배송비를 더할 때 reduce 함수를 활용한 게 좋은 방식인 것 같았다.
🔍 실패한 풀이
사실 처음에는 조금 다른 식으로 풀려고 했는데 배열 다루기가 예상대로 동작하지 않아서 화를 씩씩 내다가(...) 위 방법을 참고했다.
원래는 1️⃣ product 배열을 가격 + 배송비 순으로 정렬한 후 2️⃣ 정렬된 배열을 복사하여 productCopy라는 배열을 생성해서 3️⃣ for문을 돌며 복사한 배열 내의 상품에 순서대로 할인 쿠폰을 적용하려고 했다.
function solution(m, product) {
product.sort((a, b) => (a[0] + a[1]) - (b[0] + b[1]));
console.log('정렬 후', product);
for (let i = 0; i < productCopy.length; i++) {
// 원본 배열을 복사해서 할인 쿠폰 적용한 것을 매번 초기화 해준다고 생각했음
const productCopy = product.slice();
productCopy[i][0] = productCopy[i][0] * 0.5;
console.log(`${i}번째`, productCopy);
}
}
let arr = [[6, 6], [2, 2], [4, 3], [4, 5], [10, 3]];
solution(28, arr);내가 예상한 위 코드의 실행 결과는 아래와 같았다.
정렬 후, [[2, 2], [4, 3], [4, 5], [6, 6], [10, 3]]
0번째, [[1, 2], [4, 3], [4, 5], [6, 6], [10, 3]]
1번째, [[2, 2], [2, 3], [4, 5], [6, 6], [10, 3]]
...
4번째, [[2, 2], [4, 3], [4, 5], [6, 6], [5, 3]]그런데 실제로 찍힌 콘솔은...
정렬 후든 몇 번째든 상관 없이 모든 배송비가 반값이 된 배열만 찍혀버림...
다른 건 그렇다쳐도 slice 함수로 배열을 복사한 직후의 콘솔에도 반토막 난 상품 가격이 찍히는 이유를 정말 정말 모르겠다 🤯
할인 쿠폰을 적용하는 productCopy[i][0] = productCopy[i][0] * 0.5; 이 라인을 지우면 정렬 후, [[2, 2], [4, 3], [4, 5], [6, 6], [10, 3]] 라고 콘솔이 정상적으로 찍히는데... 왜 이렇게 나오는 건지 감이 하나도 안 잡혀서 미치겠다 🤯
array1 = [1, 2, 3, 4, 5];
array2 = array1.slice();
console.log('array1', array1);
console.log('array2', array2);
for (let i = 0; i < array2.length; i++) {
array3 = array1.slice();
array3[i] = array3[i] * 0.5;
console.log(`${i}번째`, array3);
}
내가 원했던 건 이런 플로우인데...
으악 고통스러워 😠
+)
배열 복사에 대해 검색하다가 읽게 된 글에서 slice는 중첩 구조 복사를 제대로 수행할 수 없다는 내용을 발견했다!
copied 가 복사된 객체라 arr 과 아무런 연관이 없어야하지만 중첩된 구조를 변경하면 원본과 복사본 모두 영향을 받는다.
알 것도 같으면서도... 그래도 맨 처음 찍은 콘솔에는 정렬된 배열이 그대로 찍혀야 하는 게 아닌가 하는 혼란스러움이... 😔
🌱 문제 출처
