Algorithm problem-Greedy01

1. 문제

• 이사를 하려고 짐을 넣을 박스를 사왔다, 박스에는 최대 2개의 짐이 들어간다
• 최대 무게 제한에 맞춰 박스에 짐을 담아 이동시킬 때 몇개의 박스가 필요한지를 리턴

2. 시도

• 수도코드를 참고하자

3. 수도코드

function movingStuff(stuff, limit) {
  // 짐을 오름차순 정렬을 해준다, 내림차순((a, b) => b - a)
  let sorted = stuff.sort((a, b) => a - b);
  // 짐을 옮길 때마다 카운팅 해줄 카운터를 선언
  let cnt = 0;
  // 정리해둔 짐을 다 옮길때까지 해줄거니까 while 사용하면 될듯
  while (sorted.length > 0) {
    // 옮기기 위한 박스를 빈 배열로 하나 선언
    let box = [];
    // 정리해둔 짐에서 박스로 하나씩 옮겨 담는다
    // 최소 1개의 짐은 담을 수 있으니 하나를 담아두고 시작
    box.push(sorted.pop());
    //console.log(box)
    // 짐은 2개 이상 담을 수 없고
    // 2개를 담았을 때의 무게가 limit를 넘어서는 안된다
    // 반복문을 통해 가장 무거운 애들부터 순회해서 박스에 이미 담아둔 무게에
    // 더했을 때에 리미트를 안 넘는 가장 큰 짐을 찾아보고 있으면 같이 빼주고
    // 다 돌아도 없으면 하나만 뺴주자
    for (let i = 0; i < sorted.length; i++) {
      if (box.length < 2 && (box[0] + sorted[i]) <= limit) {
        box.push(sorted[i]);
        let front = sorted.slice(0,i);
        let rear = sorted.slice(i+1);
        sorted = [...front, ...rear]
        //console.log(sorted)
      }
    }
    cnt++;
  }
  return cnt;
}

4. 레퍼런스

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