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

 

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

프로그래머스

 

문제 설명

사람들의 무게를 담은 배열과 구명보트 1개가 최대로 담을 수 있는 무게의 한계값(limit)이 주어짐

이를 토대로 필요한 구명보트 수의 최솟값을 구해야 함

단, 구명보트에는 최대 2명만이 탑승할 수 있음

 

풀이법 구상

무게 배열을 정렬하고, 가장 큰 값과 작은 값을 더해서 limit을 넘는지 안 넘는지를 토대로 개수를 구함

 

[큰 값과 작은 값을 더했을 때 limit 이하인 경우]

-> 두 사람(큰 값, 작은 값)이 보트 하나에 탔다고 치고, 큰/작은 값에 해당하는 인덱스를 한 칸씩 이동 + 새로운 구명보트 꺼냄(카운트 1 증가)

 

[큰 값과 작은 값을 더했을 때 limit 초과인 경우]

-> 한 사람(큰 값)만 보트에 태우고, 큰 값에 해당하는 인덱스를 한 칸 이동 + 새로운 구명보트 꺼냄(카운트 1 증가)

 

코드 구현 (Java)

 

import java.util.*;

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