[알고리즘] 프로그래머스: 구명보트

프로그래머스 탐욕법(Greedy): 구명보트

문제 해석

• 보트에는 한 번에 최대 2명씩 탈 수 있고, 무게 제한 있음
• 보트를 최대한 적게 사용해서 모든 사람 구출

주요 로직

1. 최대한 가장 가벼운 사람과 가장 무거운 사람을 묶어서 보트에 태우면 사용하는 보트의 개수가 최소가 됨

2. 가장 가벼운→무거운 사람 순으로 오름차순 정렬

3. 첫번째 인덱스(가장 가벼운 사람)와 마지막 인덱스(가장 무거운 사람)를 더하면서 limit과 비교

   • 최소 + 최대 > limit: 가장 무거운 사람은 나머지 다른 사람과 같이 타도 limit 초과이기 때문에 무조건 혼자만 보트 탑승 가능!

문제 해결

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
	// 가장 가벼운->무거운 순으로 정렬
	Arrays.sort(people);
	int len = people.length;
	int cnt = 0;
	
	// 최대한 가장 가벼운 사람 + 가장 무거운 사람의 조합으로 넣기 위해 양쪽 끝에서부터 이동
	// 둘의 합이 limit을 초과하면 가장 무거운 사람은 나머지 다른 사람들과 같이 타도 무조건 limit 초과
	int leftIdx = 0, rightIdx = len - 1;
	int boat = 0;
	while (cnt < len) {
		if (people[leftIdx] + people[rightIdx] <= limit) {
			leftIdx++; rightIdx--;
			cnt += 2;
		} else { 
			rightIdx--;
			cnt++;
		}
		boat++;
	}
	
	return boat;
    }
}

주의할 점

• 가장 가벼운 사람 + 가장 무거운 사람의 조합으로 해야 보트의 개수가 최소가 된다는 사실
• 둘을 더해서 limit을 초과하면 가장 무거운 사람은 보트에 탈 수 있는 가장 가벼운 사람과 더했기 때문에 결국 다른 어떤 사람과도 함께 탈 수 없다는 사실이 중요 포인트!