[Javascript] 프로그래머스 - 구명보트

문제 설명

각 사람의 몸무게가 담긴 배열 people과 보트의 무게 제한 limit이 주어질 때, 모든 사람을 구출하기 위한 최소한의 보트 수를 구하는 문제입니다. 보트는 한 번에 최대 2명까지 태울 수 있으며, 그들의 몸무게 합이 limit을 초과하면 안 됩니다.

---

제한 사항

• 1 ≤ people.length ≤ 50,000
• 40 ≤ people[i] ≤ 240
• 40 ≤ limit ≤ 240
• 구할 값: 최소한의 보트 수

---

해결 방법

알고리즘: 그리디 + 투 포인터

1. 정렬: 사람들을 몸무게 기준으로 오름차순 정렬합니다.
2. 투 포인터 활용: 가장 가벼운 사람(left)과 가장 무거운 사람(right)을 비교하며 보트에 태울 수 있는지 판단합니다.
   • 두 사람의 합이 limit 이하라면 함께 태우고 left를 증가시킵니다.
   • limit을 초과하면 무거운 사람(right)만 태우고 보냅니다.
   • 보트를 사용했으므로 answer를 증가시킵니다.
3. 반복 종료: left가 right보다 커지면 종료합니다.

---

시간 복잡도

• 정렬: O(N log N)
• 탐색: O(N) (투 포인터 사용)
• 총 시간 복잡도: O(N log N)

---

구현 코드

function solution(people, limit) {
  let answer = 0;

  people.sort((a, b) => a - b);

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

  while (left <= right) {
    if (people[left] + people[right] <= limit) {
      ++left;
    }
    --right;
    ++answer;
  }

  return answer;
}