2021.8.6 TIL 졸업선물,k번째합,두 배열 합치기

졸업 선물

학생에게 한정된 예산으로 가장 많은 선물을 할 수 있는 경우의 수는?

• 50% 할인 쿠폰을 한 번만 쓸 수 있다. 배송비 적용 안됨
• 상품값과 배송값으로 이루어진 배열이 주어진다.
• 매개변수는 배열과 선생님의 예산이다.

 

function solution(arr, num) {
  let answer;
  // code here;
  return answer;
}

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

 

틀린 답)

• 최대 상품의 값을 구하고 그 값을 50% 할인한다.
• 그 후 상품값과 배송값을 더 한 배열을 만든다.
• 그 배열을 작은 수 순으로 정렬하고
• 예산 안에서 가능한 경우를 구한다.

=> 틀린 이유 : 최대 상품 값을 구해서 할인했는데, 예산 안에서 불가능해서 그 할인한 상품을 못 사게 되는 경우의 수가 존재하기 때문이다.

 

답)

• 상품값 + 배송비 높은 차순으로 배열을 정렬한다
• 각각의 원소를 선택하여 할인 하고, 구매 항목으로 선정한다.
• 할인한 상품을 제외하고 얼마나 더 구매할 수 있는지 체크한다.
• 가장 많이 구매할 수 있는 경우의 수를 리턴한다.

 

function solution(arr, num) {
  let answer = 0;
  let n = arr.length;
  
  arr.sort((a, b) => (a[0]+ a[1]) - (b[0] + b[1]));
  
  for(let i = 0; i < n; i++) {
    let cnt = 1, sum = arr[i][0] / 2 + arr[i][1];
    for(let j = 0; j < n; j++) {
      if(i === j) continue;
      if(sum + arr[j][0] + arr[j][1] > num) break;
      sum += arr[j][0] + arr[j][1];
      cnt++;
    };
    answer = Math.max(answer, cnt);
  }
  return answer;
}

 

 

k 번째 3 수의 합

주어진 배열의 3 개의 원소를 뽑아 더한 합을 큰 수 순으로 정렬했을 때, k 번째는 무엇인가?

 

function solution(arr, k) {
  let answer;
  // code here;
  return answer;
}

let arr = [13, 15, 34, 23, 45, 65, 33, 11, 26, 42];
console.log(solution(arr, 3)); // 143

 

 

답)

 

function solution(arr, k) {
  let answer, tmp = [];
  let n = arr.length;
  
  for(let i = 0; i < n; i++) {
    for(let j = i + 1; j < n; j++) {
      for(let s = j + 1; s < n; s++) {
        let sum = arr[i] + arr[j] + arr[s];
        tmp.push(sum);
      }
    }
  };
  
  tmp.sort((a, b) => -a + b);
  answer = tmp[k - 1];
  
  return answer;
}

 

 

답2) Set()를 이용

 

function solution (arr, k) {
  let answer, tmp = new Set();
  let n = arr.length;
  
  for(let i = 0; i < n; i++) {
    for(let j = i + 1; j < n; j++) {
      for(let s = j + 1; s < n; s++) {
        let sum = arr[i] + arr[j] + arr[s];
        tmp.add(sum);
      }
    }
  };
  
  answer = Array.from(tmp).sort((a, b) => -a + b);
  return answer[k - 1];
}

 

 

두 배열 합치기

오름차순으로 정렬이 된 두 배열이 주어질 때, 오름차순으로 합친 배열 출력.

• concat() , sort() 등 배열 내장 함수 사용 제한

 

function solution(arrA, arrB) {
  let answer;
  // code here;
  return answer;
}
let a = [1, 3, 5];
let b = [2, 3, 6, 7, 9];
console.log(solution(a, b)); 
//[1, 2, 3, 3, 5, 6, 7, 9]

 

 

답)

 

function solution(arrA, arrB){
  let answer = [];
  let lenA = arrA.length;
  let lenB = arrB.length;
  let pA = pB = 0;
  
  while(pA < lenA && pB < lenB) {
    arrA[pA] <= arrB[pB] ? answer.push(arrA[pA++]) : answer.push(arrB[pB++]);
  };
  
  while(pA < lenA) {
    answer.push(arrA[pA++]);
  };
  
  while(pB <lenB) {
    answer.push(arrB[pB++]);
  };
  
  return answer;
}