[프로그래머스] 구명보트
문제
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 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 |
풀이
이번 문제는 Greedy 알고리즘으로 분류된 구명보트라는 문제이다.
A greedy algorithm always makes the choice that looks best at the moment. Link
Greedy 알고리즘 류의 문제가 어려운 점은 문제를 보고 Greedy 알고리즘을 써야한다는걸 알아채기 힘들뿐만 아니라 Greedy 알고리즘을 쓴다고 해서 항상 최적의 해를 도출한다고 할 수 없기 때문에, 이를 증명해낼 필요가 있기 때문이다.
Greedy인지 아닌지를 판단해야할 때 생각할 것은 아래와 같다.
- 하나의 큰 문제를 여러개의 작은 문제로 나눠 풀어야하는가?
- 매번 선택을 내릴때 최적의 해가 존재하는가?
사실 말이 좀 어렵고 봐도 Greedy인지 아닌지 판단내리기 쉽지 않기 때문에 그저 많이 풀어보는 방법밖에 없는 것 같다.
문제로 넘어가자!
이 문제를 어떻게하면 풀 수 있을지 가만히 생각해보았다.
문제의 목표는 구명보트 개수의 최솟값을 구하는 것 이다.
즉 어떻게 사람들을 짝지어 태우면 가장 적은수의 구명보트로 모두 탈출할 수 있을지를 생각해야하는 것이다.
내가 생각한 전략은 한 보트에 두 사람을 태우는 가장 최적의 선택은 둘이서 보트를 탈 수 있는 사람중 가장 무거운 사람을 태우도록 하는 것이다.
예를들면 [10,50,90,70]이 있고 무게제한이 100이라고 할 때, 10+90 이렇게 두명을 같이 태우는 것이 제일 낫다는 것 이다.
이제 해야할 것은 둘이서 보트를 탈 수 있는 사람중 가장 무거운 사람을 태우도록 하는 것을 반복할 때 결과적으로 최적의 값을 찾을 수 있는 것을 증명하는 일이다.
- 어차피 보트를 같이 탈 수 있는 짝이 없는 사람은 혼자서 한 보트를 타야만 한다.
- 중간정도 무게와 가벼운 사람들은 보트에 같이 탈 수 있는 짝이 많지만 무게가 무거운 사람들은 같이 보트를 탈 수 있는 짝이 한정되어있다.
- 그래서 짝이 한정되어있는 사람들을 먼저 짝지어주는것이 더 최적이다 (아마도).
내가 할 수 있는건 요정도인것같다..
이제 코드로 작성해보자!
내가 해야하는 것은 둘이서 보트를 탈 수 있는 사람중 가장 무거운 사람을 태우도록 하는 것을 반복하는 것이다.
가벼운 사람과 무거운 사람을 짝을 짓고 보트에 탈 수 있는지 없는지 판단해야하니까.. 주어진 people을 오름차순으로 정렬하고 왼쪽과 오른쪽 두개의 Pointer를 사용하고 옮겨가며 조건을 확인하면서 짝을 지으면 된다.
이를 코드로 옮기면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(people, limit):
answer = 0
people.sort()
left = 0
right = len(people)-1
while left <= right:
# 짝수 홀수
if people[left] + people[right] <= limit:
answer += 1
left += 1
right -= 1
else:
right -= 1
answer += 1
return answer