[완전탐색(블루투포스)] - 졸업 선물

[자료] - JS알고리즘 참고자료 및 시작세팅

 

문제

 

let arr = [ [6, 6], [2, 2], [4, 3], [4, 5], [10, 3] ];

solution(28, arr)

 

arr[0]의 배열 요소는 

6(상품가) 6(배송비)

2(상품가) 2(배송비) 를 나타낸다

배열길이는 학생 수 를 나타낸다.

 

solution의 28은 선생님의 구매예산이다.

최대 몇 명에게 선물을 사줄 수 있을까?

전제조건: 상품가격을 1번에 한해서 50% 할인 받을 수 있다. 배송비는 포함X && 상품가는 항상 짝수이다.

 

풀이1

먼저 배열을 총비용을 기준으로 오름차순 재정렬을 한다.

6 6  -> 2 2

2 2  -> 4 3

4 3  -> 4 5

4 5  -> 6 6

10 3 -> 10 3

 

그리고 할인을 하나씩 해보면서 모든 경우의 수(완전탐색)를 다 확인한다.

2 2 가 할인받을때 물건 몇 개 살 수 있나?

4 3 가 할인받을때는?

4 5 가 할인받을 떄는? ..... 끝까지 확인

 

 

코드1

function solution(m, product){
  let answer=0;
  let student = product.length; //5 명
  product.sort((a, b) => (a[0]+a[1]) - (b[0]+b[1])); //총비용 오름차순 재정렬
  //console.log(product); // [ [2, 2], [4, 3], [4, 5], [6, 6], [10, 3] ]
  
  for (let i = 0; i < student; i++) { //i번째 상품을 할인받는다
    let money = m- (product[i][0]/2 + product[i][1]); //할인 받은 상품은 산걸로 가정함, money는 남은 예산을 말한다
    let count = 1; //할인받은건 샀으니 1부터 시작
    for (let j = 0; j < student; j++) {
      if (j !== i && (product[j][0]+product[j][1]) > money) break;
        //i는 할인된거 이미 샀으니 조건 추가
      if (j !== i && (product[j][0]+product[j][1] <= money)) { 
        money -= product[j][0]+product[j][1];
        count++;
      }
    }
    answer = Math.max(answer, count);
  }

  return answer;
}

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

 

 

풀이2

result를 빈배열로 선언한다.

product의 반복문을 돌리고 할인을 하나씩 해보면서 모든 경우의 수(완전탐색)를 다 확인한다.

인덱스를 하나씩 상품가격을 50%할인 시킨다.

그리고 상품가격 + 배송비를 합한 새로운 배열을 만든다.

이 배열을 오름차순으로 정렬한다.

또 반복문을 돌리면서 예산으로 살 수 있는 개수를 체크한다.

반복문을 다돌리고 count 값을 result배열에 push한다.

50%할인한 상품가격을 다시 원상복구 시킨다. -> 위의 반복문 으로 돌아간다.

 

마지막엔  result 배열안에서 Math.max로 리턴해준다

 

코드2

function solution(m, product) {
    let result = [];
    for (let i = 0; i < product.length; i++) {
        let money = m; //예산
        let count = 0; //카운트 수
        product[i][0] = product[i][0] * 0.5 //상품가격 50% 할인

        //상품가격 + 배송비 의 합으로 새로운 배열을 만들고
        //오름차순으로 정렬
        let sortedArr = product
            .map((value) => value.reduce((acc, cur) => acc + cur))
            .sort((a, b) => a - b);
        //console.log(sotedArr); // (5) [4, 7, 9, 9, 13] //(5) [3, 7, 9, 12, 13] // (5) [4, 5, 9, 12, 13] // (5) [4, 7, 7, 12, 13] // (5) [4, 7, 8, 9, 12]
        //예산으로 살 수 있는 개수 체크
        for (let j = 0; j < sortedArr.length; j++) {
            if (sortedArr[j] > money) {
                break;
            }
            money -= sortedArr[j];
            count++;
        }
        result.push(count);

        //할인했던 상품가격 다시 원래 가격으로 바꿔주기
        product[i][0] = product[i][0] * 2;
    }
    return Math.max(...result);
}

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

 

 

출처

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의