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

문제 : 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요

 

풀이 : 구명 보트를 최대한 적게 사용해야 하므로, 가장 가벼운 사람 + 가장 무거운 사람을 같이 태울 수 있는지가 중요한 문제이다.

1. 오름차순 정렬 후
2. 가장 가벼운 사람 + 가장 무거운 사람 <=limit 일 때, 두 명을 동시에 태움
3. 같이 못탄다면 무거운 사람 혼자 보냄
4. 배는 무조건 한 척 출발하므로 answer 수행

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people); // 오름차순 정렬
        int left =0 ; //가장 가벼운 사람
        int right = people.length-1; // 가장 무거운 사람
        while(left<=right){
            if(people[left]+people[right]<=limit){
                left++; // 가벼운 사람 태움 (인덱스 이동)
            }
            right--; //무거운 사람은 같이 타든 혼자 타든 이번 배에 무조건 나감
            answer++;
        }
            return answer;
    }
}

 

---

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42885