[프로그래머스 (Java)] 구명보트

https://programmers.co.kr/learn/courses/30/lessons/42885?language=java 

코딩테스트 연습 - 구명보트

Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다.

한번 배를 띄울때 최대한 무게를 많이 채우는 과정을 계속 반복해 나가면 전체적으로 최적해를 구할 수 있습니다.

사람을 몸무게 순서로 정렬하고, 몸무게가 적게 나가는 순서대로 배에 태울 사람을 선택합니다.

몸무게가 30인 사람 A 가 선택된다면 사람 A 와 같이 배를 태울 수 있는 사람이 있는지 몸무게 많은 사람부터 조사합니다.

현재 사람 A 는 남은 사람들 중에서 가장 몸무게가 적게 나가는 사람입니다. 따라서 사람 A 와 함께 탈 수 없을 정도로 몸무게가 많이 나가는 사람들은 남은 그 누구와도 함께 보트를 탈 수 없고 따라서 혼자 보트를 타야합니다.

만약 사람 A 와 같이 탈 수 있는 사람 B 를 찾는다면 사람 A 와 사람 B 를 함께 보트에 태워 보냅니다.

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int answer = 0;
        int lastIdx = people.length - 1;
        for (int i = 0; i <= lastIdx; i++) {
            while (i < lastIdx && people[lastIdx] + people[i] > limit) {
                lastIdx--;
                answer++;
            }
            lastIdx--;
            answer++;
        }
        return answer;
    }
}