문제 설명
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명
씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70Kg, 50Kg, 80Kg, 50Kg] 이고 구명보트 무게 제한이 100Kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게 합은 150Kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people
과 구명보트의 무게 제한 limit
가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40Kg 이상 240Kg 이하입니다.
- 구명보트의 무게 제한은 40Kg 이상 240Kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
입출력 예
people | limit | return |
---|---|---|
[70, 50, 80, 50] | 100 | 3 |
[70, 80, 50] | 100 | 3 |
Solution
부분해의 최적해가 전체의 최적해가 되는 Greedy 알고리즘이다.
각 보트는 최대 두명
까지만 태울 수 있기 때문에 1명 또는 2명이 탑승 가능하다.
그러나 무턱대고 people
배열에서 순서대로 뽑아서 limit
을 넘는지 검사하는 방식으로는 원하는 결과를 얻을 수 없다.
코드를 작성하기 전에 생각해보자. 배열에서 최대한 limit
에 가깝게 추출하기 위해서는 어떤 방법이 필요할까?
바로 가장 무거운 사람
과 가장 가벼운 사람
을 함께 추출하는 것이다. 가장 무거운 사람은 가장 가벼운 사람과 함께 동승할 수 없다면 다른 누구와도 동승할 수 없다. 즉, 가장 무거운 사람과 가장 가벼운 사람을 함께 추출하는 방식이 부분해의 최적해이자 전체의 최적해가 되는 것이다.
접근법만 파악되었다면 코드는 간단하다.
Code
코드를 보면 알 수 있듯 먼저 people
배열을 오름차순으로 정렬한다.
이후 가장 가벼운 사람의 인덱스를 표시하는 start
와 가장 무거운 사람의 인덱스를 표시하는 last
로 두 사람을 추출한다.
만일 lightPerson + heavyPerson <= limit
이라면 두 명을 구명보트에 동승시키고, lightPerson + heavyPerson > limit
라면 heavyPerson
만 구명보트에 탑승시킨다.
이렇게 진행되다가 마지막에 만일 start == last
가 되는 상황이 오면 한 사람만이 남았다는 의미이므로 lastBoarded
변수를 1로 변경해준다.
최종값을 반환할 때 lastBoarded
가 1이라면 아직 탑승하지 못한 사람이 한 명 있다는 의미이므로 lifeBoats
변수에 1을 더해준 후 반환한다.
몇줄 평
가장 가벼운 사람 + 가장 무거운 사람 <= 제한 무게
라는 접근법만 파악된다면 어렵지 않은 문제였다.
참고 및 출처
- 프로그래머스