문제 요약
무인도에 갇힌 사람들을 구명보트로 구출해야 한다.
구명보트에는 다음 제한이 있다.
- 한 번에 최대 2명까지 탈 수 있다.
- 보트마다 무게 제한이 있다.
사람들의 몸무게 배열 people과 구명보트의 무게 제한 limit가 주어졌을 때, 모든 사람을 구출하기 위해 필요한 구명보트의 최소 개수를 구해야 한다.
핵심 아이디어
이 문제는 그리디로 해결할 수 있다.
핵심은 다음과 같다.
가장 무거운 사람을 태울 때, 함께 태울 수 있는 가장 가벼운 사람을 같이 태운다.
가장 무거운 사람은 반드시 어떤 보트에는 타야 한다.
이때 가장 가벼운 사람과도 같이 탈 수 없다면, 다른 누구와도 같이 탈 수 없다.
따라서 가장 무거운 사람은 혼자 타야 한다.
반대로 가장 가벼운 사람과 같이 탈 수 있다면 둘을 같이 태우는 것이 이득이다.
정렬과 투 포인터
먼저 사람들의 몸무게를 오름차순으로 정렬한다.
people.sort()그다음 두 포인터를 사용한다.
left = 0
right = len(people) - 1left: 가장 가벼운 사람right: 가장 무거운 사람
매번 가장 무거운 사람 people[right]는 반드시 보트에 태운다.
그리고 가장 가벼운 사람 people[left]와 함께 탈 수 있는지 확인한다.
if people[left] + people[right] <= limit:
left += 1둘이 함께 탈 수 있다면 가벼운 사람도 같이 태웠으므로 left를 오른쪽으로 이동한다.
가장 무거운 사람은 항상 태웠으므로 right는 왼쪽으로 이동한다.
right -= 1보트는 한 대 사용했으므로 정답을 1 증가시킨다.
answer += 1왜 이 방법이 최적인가?
가장 무거운 사람을 기준으로 생각해보자.
가장 무거운 사람은 남은 사람 중 누구와 같이 타더라도 무게 제한을 넘기기 쉽다.
이때 가장 가벼운 사람과도 같이 탈 수 없다면, 더 무거운 사람과는 당연히 같이 탈 수 없다.
따라서 가장 무거운 사람은 혼자 타는 것이 확정된다.
가장 가벼운 사람 + 가장 무거운 사람 > limit
=> 가장 무거운 사람은 누구와도 같이 탈 수 없음반대로 가장 가벼운 사람과 같이 탈 수 있다면, 둘을 같이 태우는 것이 좋다.
가장 무거운 사람을 혼자 태우는 것보다 보트 한 대에 두 명을 태울 수 있기 때문이다.
이 선택은 이후에 손해를 만들지 않는다.
따라서 매 순간 가장 무거운 사람을 처리하는 그리디 방식이 최적이다.
전체 코드
def solution(people, limit):
people.sort()
left = 0
right = len(people) - 1
answer = 0
while left <= right:
if people[left] + people[right] <= limit:
left += 1
right -= 1
answer += 1
return answer시간 복잡도
사람들의 몸무게를 정렬하는 데 시간이 가장 많이 든다.
O(n log n)정렬 후 투 포인터 탐색은 한 번만 진행한다.
O(n)따라서 전체 시간 복잡도는 다음과 같다.
O(n log n)공간 복잡도
추가로 사용하는 변수는 포인터와 정답 변수 정도다.
O(1)단, 파이썬의 정렬 내부 구현에 따른 추가 공간은 별도로 사용될 수 있다.
정리
이 문제는 최대 2명까지만 보트에 탈 수 있다는 조건이 중요하다.
그래서 가장 무거운 사람을 기준으로 매번 처리할 수 있다.
풀이 흐름은 다음과 같다.
- 몸무게를 오름차순으로 정렬한다.
- 가장 가벼운 사람과 가장 무거운 사람을 가리키는 포인터를 둔다.
- 둘이 같이 탈 수 있으면 함께 태운다.
- 같이 탈 수 없으면 가장 무거운 사람만 태운다.
- 매번 보트 수를 1 증가시킨다.
가장 무거운 사람을 가장 가벼운 사람과도 태울 수 없다면 혼자 타야 한다는 점이 이 문제의 핵심이다.
