[JAVA] 프로그래머스 : 구명보트 (코딩테스트 고득점 kit > 탐욕법(Greedy))

https://programmers.co.kr/learn/courses/30/lessons/42885

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

탐욕법은 최적의 해에 도달하기 위한 문제 해결 방안이 필요하다.

 

해결 방안

1. 제일 무거운 사람과 제일 가벼운 사람이 limit에 걸리지 않으면 둘다 나가고 아니면 무거운 사람부터 나가도록 구현함

 

코드

import java.util.*;
// 구명보트
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        
        // 몸무게가 적게 나가는 사람 index
        int index = 0;
        for(int i = people.length-1; i>=index; i--){
            
            // 최대 최소 합이 limit보다 크면 제일 무거운사람 먼저 보냄
            if(people[i] + people[index] > limit){
                answer++;
                
            }
            // 최대 최소 합이 limit 보다 작거나 같으면 둘다 보냄
            else{
                index++;
                answer++;
            }
        }
        
        return answer;
    }
}