[프로그래머스] 구명보트 (그리디 탐욕법)

🫡 문제

프로그래머스 - 구명보트

🫡 코드

import java.util.*;

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

🫡 풀이

GREEDY 탐욕법 알고리즘

각 단계에서 가장 최적인 선택을 하여 문제를 해결하는 알고리즘

구명보트를 최대한 적게 사용해야 하기 때문에
구명보트 하나에 100kg와 가까운 몸무게를 가진 사람(1명 or 2명)을 태워야함

1. people 정렬
2. 가장 작은 몸무게와 가장 큰 몸무게를 더했을 때 100kg 보다 크면 가장 큰 몸무게는 구명보트 1개에 혼자 태워야 하고, 가장 작은 몸무게와 두번째로 큰 몸무게를 더해줘야함 ( 이런식으로 큰 몸무게를 줄여나감)
3. 가장 작은 몸무게와 가장 큰 몸무게를 더했을 때 100kg와 같거나 작으면 구명보트 1개에 2명을 태울 수 있기 때문에 두번째로 작은 몸무게와 그 다음으로 큰 몸무게를 더해주는 식으로 코드를 작성했다

서핑하고 와서 괜히 구명보트 문제 풀고싶었다는 건 안비밀 ㅎ