1. 문제

💡 You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

• people, limit 파라미터를 받는데 people은 number 배열이고 people[i]는 무게를 나타낸다.
• 무한한 boat가 주어지는데 최대 2명이 탈 수 있고, 파라미터로 주어진 limit보다 무게가 적어야한다.
• 모든 사람을 태우기위해 필요한 보트의 최소 갯수를 구하라.
• 1 ≤ people[i] ≤ limit

2. 잘못된 첫 번째 접근법

처음 문제를 봤을 때 오름차순으로 정렬한 후 한명씩 앞에서부터 태워야겠다 생각했는데, 보트는 최대 2명만 탈 수 있다는 조건을 고려하지 못했다..! 그리고 최대 2명만 태우더라도 문제가 생긴다.

만약, people = [5, 1, 4, 2], limit = 6 조건일 때 (1, 2) (4) (5) 3개의 보트가 필요하지만 실제로는 (1, 5) (2, 4) 두 개의 보트만 있어도 된다.

3. 두 번째 접근법

오름차순으로 정렬한 후 2 Pointer를 사용해서 무게가 가장 적게 나가는 사람, 무게가 가장 많이 나가는 사람을 묶어서 태우면 가장 효율적으로 탈 수 있겠다고 생각했다.

그리고 두 사람을 태웠을 때 조건을 두가지 분기로 나눴다.

1) 두 사람의 무게가 limit보다 클 때

이 경우 가장 무게가 많이 나가는 사람은 가장 무게가 적게 나가는 사람 외에 그 누구와 태워도 limit을 초과해 버리므로 혼자 태워서 보내야한다.

2) 두 사람의 무게가 limit보다 작거나 같을 때

무게의 합이 limit과 같으면 가장 효율적인 조합이므로 두 사람을 태워 보낸다.

무게의 합이 limit보다 작으면 무게가 가장 적게 나가는 사람보다 조금 더 나가는 사람을 태워 limit에 맞출 수도 있을 것이다. 그런데, 굳이 그럴 필요는 없다.

만약 people = [1, 1, 1, 2, 98, 98], limit = 100 이라고 가정하면 1 + 98보다 2 + 98로 100을 맞추는게 가장 효율적으로 보이지만, 98 한명을 태워 보내면 그 다음 가장 무거운 사람은 98보다 작거나 같다. 결국 2보다 무게가 적게 나가는 사람은 98보다 무게가 큰 사람과 어울려야 효율적인데 98보다 큰 사람이 남아있을 수 없는 상태이므로 고려할 필요 없이 limit보다 작으면 바로 두명을 태우면 되는 것이다.

3. 작성된 코드

function numRescueBoats(people, limit) {
  /*
    여기선 파라미터인 people 배열을 그대로 오름차순 정렬하지만, 만약 배열의 불변성을 유지해야 한다면
    .slice() 또는 전개 연산자로 깊은 복사 후 sort한 배열을 변수에 담아 사용한다.
  */
  people.sort((a, b) => a - b);

  let minIndex = 0; // 가장 가벼운 사람의 순서
  let maxIndex = people.length - 1; // 가장 무거운 사람의 순서
  let count = 0; // 필요한 boat의 수

  while (minIndex <= maxIndex) { 
    if (minIndex === maxIndex) { // 한 명이 남았을 때는 혼자 태우고 종료시킨다.
      count += 1;
      break;
    }
    const minWeight = people[minIndex];
    const maxWeight = people[maxIndex];

    if (minWeight + maxWeight > limit) {
      count += 1;
      maxIndex -= 1;
    } else {
      count += 1;
      minIndex += 1;
      maxIndex -= 1;
    }
  }

  return count;
};