[Greedy] 짐 나르기

짐 나르기

문제

김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다.

예를 들어, 짐의 무게가 [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개 이하입니다.
• 박스의 무게 제한은 항상 짐의 무게 중 최대값보다 크게 주어지므로 짐을 나르지 못하는 경우는 없습니다.

입출력 예시

let output = movingStuff([70, 50, 80, 50], 100);
console.log(output); // 3

let output = movingStuff([60, 80, 120, 90, 130], 140);
console.log(output); // 4

문제풀이

function movingStuff(stuff, limit) {
// 1. 입력 배열의 순서를 변경하지 않고 복사한 배열을 생성하고 내림차순으로 정렬 (가장무거운 > 가장가벼운)
  const sortedStuff = [...stuff].sort((a, b) => b - a);

  let leftIdx = 0; // 왼쪽 끝 인덱스(가장 무거운 짐)
  let rightIdx = sortedStuff.length - 1; // 오른쪽 끝 인덱스(가장 가벼운 짐)
  let count = 0; // 필요한 박스의 수

  // 왼쪽 끝 인덱스가 오른쪽 끝 인덱스보다 작을 때까지 반복
  while (leftIdx < rightIdx) {
    const leftItem = sortedStuff[leftIdx]; // 왼쪽 아이템
    const rightItem = sortedStuff[rightIdx]; // 오른쪽 아이템

    // 왼쪽 아이템과 오른쪽 아이템을 합쳐서 박스 무게 제한을 넘지 않으면,
    // 왼쪽 인덱스를 증가시키고 오른쪽 인덱스를 감소시키면서 필요한 박스의 수를 1 증가시킨다.
    if (leftItem + rightItem <= limit) {
      rightIdx--;
    }
    leftIdx++;
    count++;
  }

  // 입력 배열의 길이가 홀수일 경우, 마지막 아이템은 한 개의 박스에 담아야 함
  if (leftIdx === rightIdx) count++;

  // 필요한 박스의 수를 반환
  return count;
}

레퍼런스 코드

function movingStuff(stuff, limit) {
  let twoStuff = 0;
  // 짐을 무게순으로 오름차순 정렬
  let sortedStuff = stuff.sort((a, b) => a - b);
  // 가장 가벼운 짐의 인덱스
  let leftIdx = 0;
  // 가장 무거운 짐의 인덱스
  let rightIdx = sortedStuff.length - 1;
  while(leftIdx < rightIdx) {
      // 가장 가벼운 짐과 무거운 짐의 합이 limit 보다 작거나 같으면 2개를 한번에 나를 수 있다
      if(sortedStuff[leftIdx] + sortedStuff[rightIdx] <= limit) {
      // 다음 짐을 확인하기 위해 가장 가벼운 짐과 무거운 짐을 가리키는 인덱스를 옮겨주고
      // 한번에 2개 옮길 수 있는 개수를 +1 해준다   
          leftIdx++;
          rightIdx--;
          twoStuff++;
      } else {
          // 위 조건에 맞지 않는 경우는 한번에 한 개만 나를 수 있는 경우이기 때문에
          // 가장 무거운 짐의 인덱스만 옮겨준다
              rightIdx--;
      }
  }
  // 전체 짐의 개수에서 한번에 2개를 나를 수 있는 경우를 빼 주면 총 필요한 박스의 개수를 구할 수 있다
  return stuff.length - twoStuff;
}