[Greedy] 최소 개수의 박스로 물건 나르기

옮겨야 하는 짐들의 무게가 배열에 나타나있다.

박스가 옮길 수 있는 물건의 개수는 최대 2개이며, 박스가 담을 수 있는 짐의 무게가 정해져있다.

짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때,

모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.

 

나의 코드(오답!)

function movingStuff(stuff, limit) {
  let cnt = 0;
   // 첫번째 물건부터 계산하기
    // 그 다음 물건부터 차례로 더해서 무게 측정
    // limit 보다 클 경우 넘어가기
    // 모두 다 넘어갔을 경우 cnt + 1
    // limit 보다 작은 경우 cnt + 1 하고 반복문 탈출

  for(let i = 0; i < stuff.length; i++){
    for(let j = i + 1; j < stuff.length; j++){
      if(stuff[i] + stuff[j] < limit){
        cnt ++;
        break;
      }
    } cnt ++;
  } return cnt;
}

reference

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;
}

코드 작성 틀린 이유

중복되는 경우가 발생할 수 있다는 사실을 인지하지 못함

 

고쳐야 할 점

나의 생각이 중복되는 경우를 발생시킬 수 있는지 먼저 생각한다.

중복이 발생 될 수 있는 경우라면, 주어진 값들을 먼저 정렬한 뒤 코드를 작성하도록 한다