[프로그래머스/Java] level2 구명보트

🚤Problem

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

Solution

• 구명보트로 사람들을 구출하기 위해 가장 적게 사용하는 구명보트의 개수를 구하는 문제이다.
• 분류는 그리디 알고리즘이다.
• 구명보트는 최대 두 명까지 탈 수 있다. 가장 최적의 경우는 몸무게가 가장 많이 나가는 사람과 몸무게가 가장 적게 나가는 사람이 타는 경우이다.
• 만약 몸무게가 가장 많이 나가는 사람과 가장 적게 나가는 사람이 무게제한 때문에 탈 수 없다면 무게가 가장 많이 나가는 사람은 혼자서밖에 탈 수 없으므로 무게가 가장 많이 나가는 사람을 구출한다.
• 모든 사람을 구출할 때까지 반복한다면 최솟값을 구할 수 있다.

Java Code

import java.util.Arrays;

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