JS 알고리즘 - sort(), Math.max()

문제

오늘 푼 자바스크립트 알고리즘 문제는 어제 푼 것보다 더 어려운 것이었다.

 

문제는 아래와 같다.

 

졸업 선물

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

▣ 입력설명
첫 번째 줄에 반 학생수 N(1<=N<=1000)과 예산 M(1<=M<=100,000,000)이 주어진다.
두 번째 줄부터 N줄에 걸쳐 각 학생들이 받고 싶은 상품의 가격과 배송비가 입력됩니다.
상품가격과 배송비는 각각 100,000을 넘지 않습니다. 상품가격은 짝수로만 입력됩니다.
▣ 출력설명
첫 번째 줄에 선생님이 현재 예산으로 선물할 수 있는 최대 학생수를 출력합니다.
선생님 최소한 1개 이상의 상품을 살 수 있는 예산을 가지고 있습니다.
▣ 입력예제 1
5 28
6 6
2 2
4 3
4 5
10 3
▣ 출력예제 1
4
출력설명
(2, 2), (4, 3), (4, 5)와 (10, 3)를 할인받아 (5, 3)에 사면 비용이 4+7+9+8=28입니다.

 

 

해답

 

그에 따른 해답은 아래와 같다.

주석 및 디버깅용 콘솔을 실행해서 잘 따라와도 바로 이해가 될 것 같다.

  function solution(m, product){
        let answer=0;
        let n=product.length;
        product.sort((a, b)=>(a[0]+a[1])-(b[0]+b[1]));
        console.log('product: ' + product)
        for(let i=0; i<n; i++){
            let money=m-(product[i][0]/2+product[i][1]);
            console.log('i: ' + i + ' & ' + 'money: ' + money) // money는 남은 예산
            let cnt=1; // 몇 개를 살 수 있는지 count
            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){
                    console.log('j: ' + j + ' & ' + 'money: ' + money)
                    money-=(product[j][0]+product[j][1]);
                    console.log('money: ' + money)
                    cnt++;
                    console.log('cnt: ' + cnt)
                }
            }
            answer=Math.max(answer, cnt);
            console.log('answer: ' + answer)
        }  
        return answer;
    }

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

 

위 문제를 풀면서 알아야 할 몇 가지 개념들을 정리해보겠다.

 

개념설명

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

 

일단 sort()를 사용하는 방법은 다음과 같다.
콜백 함수가 동작하는 방식에 따라 양수를 반환하면: 첫 번째 인자의 위치가 두 번째 인자보다 뒤에 오도록 둘의 위치를 바꾼다.
음수를 반환하면: 첫 번째 인자의 위치가 두 번째 인자보다 앞에 오도록 둘의 위치를 그대로 둔다.
0을 반환하면: 두 인자의 위치를 변경하지 않는다.

따라서, (a, b) => a - b 형태의 콜백 함수를 사용하면
a가 b보다 큰 경우 (즉, a - b가 양수일 경우): a와 b의 위치를 바꾼다.
a가 b보다 작은 경우 (즉, a - b가 음수일 경우): a와 b의 위치를 그대로 둔다.
a와 b가 같은 경우: 위치를 변경하지 않는다.
이렇게 동작하므로, 배열은 오름차순으로 정렬된다.

 

해당 문제의 답변에 sort()를 사용한 이유는 상품의 가격과 배송비 합계를 기준으로 오름차순으로 정렬하기 위해서이다.

이렇게 하면 최소 비용의 상품부터 최대 비용의 상품까지 순서대로 정렬할 수 있다.

 

sort()의 오름차순 정렬

let arr = [10, 2, 15, 1];
arr.sort((a, b) => a - b);
console.log(arr); // 출력: [1, 2, 10, 15]

 

 

sort()의 내림차순 정렬

let arr = [10, 2, 15, 1];
arr.sort((a, b) => b - a);
console.log(arr); // 출력: [15, 10, 2, 1]

 

 

answer=Math.max(answer, cnt); 

Math.max(answer, cnt)는 answer와 cnt 중에서 더 큰 값을 반환하는 문법이다.

따라서 위 문장은 answer 값과 cnt 값을 비교하여 더 큰 값을 answer에 저장하는 역할을 저장하고, 항상 최대 값을 유지하게 되면서 for문이 끝나고 가장 많은 cnt 수가 무엇인지 알 수 있도록 하는 역할을 한다.