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

 

문제

프로그래머스

 

알고리즘

그리디, 투 포인터

 

풀이

몸무게가 가장 큰 사람을 항상 구명보트에 태우면서

몸무게가 가장 작은 사람을 같이 태울 수 있다면 같이 태우는 방법이 항상 구명보트를 제일 적게 쓸 수 있다.

 

따라서 몸무게를 오름차순으로 정렬한 후

남아있는 사람의 몸무게 중 가장 낮은 몸무게의 인덱스를 가리키는 left 와

남아있는 사람의 몸무게 중 가장 큰 몸무게의 인덱스를 가리키는 right 를 정하고,

 

모든 사람을 다 태울때까지 (left > right) 

구명보트를 하나 사용(answer++)하면서 몸무게가 가장 높은 사람을 태우고(right--)

몸무게가 가장 낮은 사람도 태울 수 있다면(people[left] + people[right] <= limit) 같이 태운다(left++)

 

코드

import java.util.*;

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