짐 나르기(Greedy)

문제

짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.

박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.

짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.

입력

인자 1: stuff

• Number 타입의 40 이상 240 이하의 자연수를 담은 배열
  • ex) [70, 50, 80, 50]

인자 2: limited

• Number 타입의 40 이상 240 이하의 자연수

출력

• Number 타입을 리턴해야 합니다.
• 모든 짐을 옮기기 위해 필요한 박스 개수의 최솟값을 숫자로 반환합니다.

주의사항

• 옮겨야 할 짐의 개수는 1개 이상 50,000개 이하입니다.
• 박스의 무게 제한은 항상 짐의 무게 중 최대값보다 크게 주어지므로 짐을 나르지 못하는 경우는 없습니다.

입출력 예시

나의 코드

결과

소스코드

function movingStuff(stuff, limit) {
  // 박스의 갯수를 셀 변수를 선언합니다.
  let count = 0;
  // 짐의 무게를 오름차순으로 정렬합니다.
  stuff = stuff.sort((a, b) => a - b);
  // 짐의 무게는 배열로 구성이 되어있습니다.
  // 짐의 무게를 위에서 오름차순으로 정렬했습니다.
  // 이 배열의 0번째 인덱스는 최솟값이 될 것입니다.
  // 마찬가지로, 마지막 인덱스는 최댓값이 됩니다.
  // 이 인덱스를 각각 left와 right라는 변수로 선언합니다.
  let left = 0;
  let right = stuff.length - 1;

  // left의 값이 right를 초과할 때 까지 반복을 수행합니다.
  while (right >= left) {
    // 만약, 배열의 최솟값과 최댓값을 더했을 때, 무게 제한 이하인 경우
    if (stuff[left] + stuff[right] <= limit) {
      // 다음 값을 알아내기 위해 left값을 1 증가합니다.
      left++;
      // right값은 -1을 감소시킵니다.
      right--;
      // 박스에 stuff[left] 와 stuff[right]을 담았으므로
      // 박스 갯수를 1 증가합니다.
      count++;
    } else {
      // 최솟값과 최댓값을 더했을 때, 무게 제한을 초과한다면
      // left는 그대로 두고, right를 1 감소합니다.
      right--;
      // 최솟값과 최댓값을 더했음에도 무게 제한을 초과한다면,
      // 그 때 right값은 같이 넣을 수 있는 짐이 없습니다.
      // 즉, right값 하나만 박스에 담기게 됩니다.
      // 박스에 담겼으므로, 박스 갯수를 1 증가합니다.
      count++;
    }
  }
  // 반복이 종료되면, 그 때의 박스 갯수를 반환합니다.
  return count;
}