[Algorithm] [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) {
  // TODO: 여기에 코드를 작성합니다.
  // 수도코드를 작성해보장.
  // 여러 요소를 합쳤을 때, limit보다 작았을 경우를 세야하는것.
  // 일단 정렬을 하고, 가장 작은것과 큰것의 합이 limit의 비교

  let sorted = stuff.sort((a,b) => a-b);
  // 가장 첫번째 있는 값을 얻기 위해서 stuff를 정렬을 한다.
  // 이후 첫번째 있는 값이 가장 작고 맨 끝에 있는 값이 크기 때문에, 두개의 합이 limit를 넘지 않으면 하나의 패킷으로 묶일 수 있게 된다.
  // 사실 이 방법이 최적의 결과를 이끌어낼지는 모르겠지만, greedy Algorithm은 limit의 최적의 결과를 찾는 것이기 때문에 limit에 가까운 값으로 다가가
  // 값을 구하는게 목표가 되겠다.

  let count = 0;
  // 가장 큰 값과 작은 값이 만나 limit보다 작아진다면 count가 1씩 증가하도록한다.

  let max = sorted.length-1
  let mini = 0


  // shift나 pop을 쓰면 원본을 건드리게 되니까 되도록이면 이러한 방법은 지향하는게 좋지 않을까하는 생각이다.
  for(let i = 0 ; mini <= max ; i++){
    if(sorted[mini] + sorted[max] > limit){
      // 두개의 합이 limit을 넘어갔을 경우 가장 큰 값 하나만 들어가기 때문에 count가 하나가 추가 된다.
      max--;
      count++;

      // 이후, 다음 큰값과 현재의 값을 더해야한다.
      // 그렇게 하려면, max가 -1이 되어야함.
      
      
    }
    else if(sorted[mini] + sorted[max] <= limit ){
      mini++;
      max--;
      count++;
    }
  }
  
  return count

}}