Lv2. 프로그래머스 구명보트

💡문제 요약

Greedy 문제로, 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하는 문제이다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있다. 구명보트를 최대한 적게 사용하여 모든 사람을 구하려고 한다.

** 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해라.

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

💡알고리즘 설계

1. 몸무게를 오름차순으로 정렬
2. 가장 무거운 사람과 가장 가벼운 사람을 확인
3. limit을 초과할 경우 무거운 사람만 구명보트에 태운 뒤 start 증가
4. 가장 무거운 사람 (start)과 가장 가벼운 사람 (end)의 합이 limit보다 작거나 같다면 둘 다 구명보트에 태운다
5. while 문을 한번 돌 때마다 무조건 구명보트가 1번 사용되므로 end--, answer 증가
6. while문의 조건(start + end ≤ limit)을 만족하지 않으면 종료