반응형
📌강의 정리
최대한 많은 학생에게 선물을 사줘야 하므로 선물 개수가 중요하다.
상품가격하고 배송비를 더한 값으로 정렬을 한다.
제일 비싼것을 할인 받는다고 반드시 많은 선물을 사는 것은 아니다.
그러므로 모든 경우를 다 봐야한다.
각 상품마다의 50퍼센트 할인을 받아 다 계산해본다.
n은 문제에서의 학생수이다.
이제 정렬을 하는데 sort를 써서 ((a,b)⇒(a[0]+a[1])-(b[0]+b[1]));
을 하면 두 값을 더한 값의 오름차순으로 정렬된다.
이제 포문을 써서 i일때 할인을 받는것으로 한다.
money 변수는 i값의 상품금액의절반과 배송비용을 총비용에서 뺀값이다.
이제 다시 포문을 돌려 i를 제외한 상품금액과 배송비용을 더한게 money보다 작아야한다.
그래야 뺄수가 있으므로
이제 money변수는 money에서 i를 제외한 상품금액과 배송비용을 더한값을 뺀다.
이후 cnt++을 하여 카운트한다.
이제 못사게되는경우는 헛바퀴를 돌므로 그 헛바퀴를 방지하는 if문을 설계해야한다.
money에서 i를 제외한 상품금액과 배송비용을 더한값이 money보다 커지면 break를 한다.
마지막으로 Math.max를 이용하여 answer에 제일 높은 카운트수가 들어가게 하면된다.
📌느낀점
문제도 어렵긴했지만 2차원배열의 브라우저에서의 디버깅이 쉽지않았다..
2차원배열은 아래에서 수정되면 위에 아직 지나가지도 않은 배열이 수정된다.
이상하다...
전체적으로 강사님과 나와의 풀이는 비슷했다.
세세한 부분의 디테일을 잘 살려서 코드를 간결하게 마무리할줄 알아야한다.
//220611 주석추가버전
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, product) {
let answer = 0;
let formArr = [];
let sum = 0;
let cnt = 0;
let max = Number.MIN_SAFE_INTEGER;
//for문을 사용해서 하나씩 돌아가며
for (let i = 0; i < product.length; i++) {
for (let j = 0; j < product.length; j++) {
//순서대로 0번 값을 절반으로 하며 한사람씩 상품과 배송비를 더해서
//새로운 배열을 만든다.
if (i === j) {
formArr.push(arr[j][0] / 2 + arr[j][1]);
continue;
}
//새로운 배열을 만든다.
formArr.push(arr[j][0] + arr[j][1]);
}
//그 배열을 정렬하고 더할때마다 cnt 하고
console.log("정렬전 = ", formArr);
formArr.sort((a, b) => a - b);
console.log("정렬후 = ", formArr);
//더할때마다 cnt 하고
for (let k = 0; k < formArr.length; k++) {
sum += formArr[k];
if (sum > m) {
cnt = k;
break;
}
cnt++;
}
//예산 넘길때 cnt값을 max에 넣어준다.
if (cnt > max) max = cnt;
sum = 0;
cnt = 0;
formArr = [];
}
//모든 반복이 끝나고 max값을 반환한다.
answer = max;
return answer;
}
let arr = [
[6, 6],
[2, 2],
[4, 3],
[4, 5],
[10, 3],
];
console.log(solution(28, arr));
</script>
</body>
</html>//나의 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr){
let answer=0;
let n = arr.length;
let max = 0;
for(let i=0; i<n; i++){
let sum = 0;
let sum2 = 0;
console.log('arr = ',arr)
let arr2 = arr.map(v=>v.slice());
console.log('arr2 = ',arr2)
arr2[i][0] = (arr2[i][0])/2
for(let j=0; j<n; j++){
arr2[j] = arr2[j][0]+arr2[j][1]
}
arr2 = arr2.sort(function(a,b){
return a-b;
})
console.log(arr2)
for(let k=0;k<arr2.length;k++){
sum+=arr2[k];
sum2=sum+arr2[k+1]
if(sum2>m){
if(max < k+1){
if(sum<=m){
max = k+1;
console.log(max)
console.log(sum)
console.log(sum2)
break;
}
}
}
}
}
answer = max;
return answer;
}
let arr=[[6, 6], [2, 2], [4, 3], [4, 5], [10, 3]];
console.log(solution(28, arr));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
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));
</script>
</body>
</html>
//나의 코드(조금 개량)
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr){
let answer=0;
let n = arr.length;
let max = 0;
for(let i=0; i<n; i++){
let sum = 0;
let sum2 = 0;
let arr2 = arr.map(v=>v.slice());
arr2[i][0] = (arr2[i][0])/2
for(let j=0; j<n; j++){
arr2[j] = arr2[j][0]+arr2[j][1]
}
arr2 = arr2.sort(function(a,b){
return a-b;
})
for(let k=0;k<arr2.length;k++){
sum+=arr2[k];
sum2=sum+arr2[k+1]
if(sum2>m && max < k+1 && sum<=m){
max = k+1;
break;
}
}
}
answer = max;
return answer;
}
let arr=[[6, 6], [2, 2], [4, 3], [4, 5], [10, 3]];
console.log(solution(28, arr));
</script>
</body>
</html>
반응형
'JS 알고리즘 문제풀이 > 섹션 4. 완전탐색(블루투포스)' 카테고리의 다른 글
| 5.K번째 큰 수 (0) | 2022.01.14 |
|---|---|
| 3.멘토링 (0) | 2022.01.14 |
| 2.뒤집은 소수 (0) | 2022.01.14 |
| 1.자리수의 합 (0) | 2022.01.14 |