LeetCode 881 - Boats to Save People (Medium)

문제

LeetCode - 881번

풀이 과정

최대 2명이 탈 수 있는 보트를 이용해서 모든 사람들을 옮기는 최소 왕복 이동 횟수를 구하는 그리디 문제입니다.

우선 사람들의 몸무게로 내림차순 정렬해서 보트에 순서대로 태우도록 합니다.
여기서 생각해볼 점은 people[head] < limit 일 때 남은 사람은 limit - people[head] 보다 적은 몸무게 중
가장 큰 무게 A 를 가지는 사람을 선택할 것인지 혹은 남은 사람들 중 가장 무게가 적게 나가는 사람 B 을 선택할 것인지 입니다.

이때 A 를 선택하든 B 를 선택하든 선택되지 않은 다른 하나를 위해 보트가 하나 필요하다는 사실은 변하지 않습니다.
따라서 가장 무게가 많이 나가는 사람을 가리키는 포인터 head 와 가장 무게가 적은 사람을 가리키는 tail 을 사용해서
모든 사람을 옮기는데 필요한 보트의 수를 구하면 됩니다.

코드

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function (people, limit) {
  people.sort((a, b) => b - a);

  let answer = 0,
    head = 0,
    tail = people.length - 1;

  while (head <= tail) {
    if (head < tail && people[head] < limit) {
      if (people[tail] <= limit - people[head]) {
        tail--;
      }
    }

    head++;
    answer++;
  }

  return answer;
};