[JS] 프로그래머스 / 탐욕법(Greedy) / 구명보트

문제

프로그래머스

핵심 아이디어

• left와 right 포인터를 사용하여 배열의 양끝에서 접근한다.
• 조건 확인: people[left]와 people[right]의 합이 limit 이하인 경우 두 사람을 한 번에 태운다. 그렇지 않으면 left에 해당하는 무거운 사람만 태운다.
• left++와 right--로 배열의 범위를 줄여 나가면서 필요한 보트의 개수를 최소화한다.
• left <= right 조건은 모든 사람을 고려하면서도 배열의 중간 지점에서 멈추기 위해 설정한 것이다.

정답

function solution(people, limit) {
  people.sort((a, b) => b - a);

  let answer = 0;
  let left = 0;
  let right = people.length - 1;

  while (left <= right) {
    const person = people[left];
    const lastPerson = people[right];

    if (person + lastPerson <= limit) {
      right--;
    }

    left++;
    answer++;
  }

  return answer;
}