사람들의 몸무게를 담은 숫자 리스트 weights와 한 대의 로켓이 실을 수 있는 최대 하중을 나타내는 값 limit이 주어진다고 가정해 보겠습니다. 각 로켓에는 최대 두 명까지만 탑승할 수 있으며, 우리는 모든 사람을 행성으로 구출하는 데 필요한 최소 로켓 수를 구해야 합니다.
예를 들어 입력이 weights = [300, 400, 300], limit = 600이라면 출력은 2가 됩니다. 몸무게가 300인 두 사람은 한 대의 로켓에 함께 태울 수 있고, 몸무게가 400인 사람은 별도의 로켓 한 대가 더 필요하기 때문입니다.
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
가장 무거운 사람부터 차례로 로켓에 태웁니다.
가장 무거운 사람이 탑승한 상태에서, 남은 사람 중 가장 가벼운 사람이 함께 탑승할 수 있는지(limit − x 이하인지) 확인합니다.
함께 탈 수 있다면 두 사람을 같은 로켓에 태우고, 그렇지 않다면 가장 무거운 사람만 혼자 보냅니다.
가장 무거운 사람이 가장 가벼운 사람과도 함께 탑승할 수 없다면 다른 누구와도 함께 탈 수 없으므로, 혼자 타는 것이 항상 최선입니다. 이를 바탕으로 문제 해결 절차를 정리하면 다음과 같습니다 −
weights 리스트를 오름차순으로 정렬합니다
cnt := 0 으로 초기화합니다
weights가 비어 있지 않은 동안 다음을 반복합니다
x := weights에서 마지막(가장 무거운) 요소를 꺼냅니다
weights가 비어 있지 않고 weights[0] <= limit − x 라면
weights에서 첫 번째(가장 가벼운) 요소를 삭제합니다
cnt := cnt + 1
cnt를 반환합니다
더 나은 이해를 위해 다음 구현 예제를 살펴보겠습니다 −
예제(Python)
class Solution:
def solve(self, weights, limit):
weights.sort()
cnt = 0
while weights:
x = weights.pop()
if weights and weights[0] <= limit - x:
weights.pop(0)
cnt += 1
return cnt
ob = Solution()
weights = [300, 400, 300]
limit = 600
print(ob.solve(weights, limit))
입력
[300, 400, 300], 600
출력
2
알고리즘 분석
리스트 정렬에 O(n log n)의 시간이 소요되며, 이후 각 사람은 정확히 한 번씩 처리되므로 전체 시간 복잡도는 O(n log n)입니다. 이 방식은 '가장 무거운 사람 + 가장 가벼운 사람'을 짝지어 판단하기 때문에 매 단계에서 최선의 선택을 하게 되며, 결과적으로 항상 최소 개수의 로켓으로 모든 사람을 구출할 수 있음이 보장됩니다.