← 9주차 · 그리디
보통그리디투 포인터정렬

구명보트

사람들의 몸무게 배열 people과 보트 한 척의 무게 제한 limit이 주어져요. 보트 한 척에는 최대 두 명까지 탈 수 있고, 두 사람의 무게 합이 limit을 넘지 않아야 해요.

모두를 태우는 데 필요한 최소 보트 수를 반환해요.

정렬한 뒤 양끝에서 짝짓는 것이 최적이에요. 가장 무거운 사람은 가장 가벼운 사람과 함께 태울 수 있으면 태우고, 아니면 혼자 보내요.

예시

예시 1
입력
people = [1, 2], limit = 3
출력
1
설명
1 + 2 = 3 ≤ 3이니 한 보트에 둘 다 태워요.
예시 2
입력
people = [3, 2, 2, 1], limit = 3
출력
3
설명
(1, 2), (2), (3) — 세 척이에요.

제한 사항

  • 1 ≤ people.length ≤ 100,000
  • 1 ≤ people[i] ≤ limit ≤ 1,000,000,000
무게 오름차순으로 정렬하고 포인터 i(가장 가벼움), j(가장 무거움)를 둬요. people[i] + people[j] <= limit이면 둘을 함께 태우고 i++, 어느 경우든 j--와 보트 수 증가를 해요.
javascript
function rescueBoats(people, limit) {
  const sorted = [...people].sort((a, b) => a - b);
  let i = 0;
  let j = sorted.length - 1;
  let boats = 0;
  while (i <= j) {
    if (sorted[i] + sorted[j] <= limit) i++;
    j--;
    boats++;
  }
  return boats;
}
이전 문제회의실 배정
다음 문제거스름돈
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.