[프로그래머스] 구명보트 (자바/그리디)

문제 설명

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

 

 

풀이 방법

가장 작은 무게와 가장 큰 무게를 더해서 그게 무게 제한보다 작은지 확인해 보면 되는 문제이다.

 

 

 

어려웠던 점

 

처음에는 정렬을 한 다음에 무게가 작은 순부터 더해서 답을 구했다.

다음과 같이 50 50 70 80이 주어지면 50+50, 70, 80 이런 식으로 작은 무게부터 2개씩 더해보고 무게 제한보다 작으면 결괏값을 갱신했다.  

 

 

그러면 주어진 입출력 예제는 맞았는데 제출해 보니 30.0/100.0 임을 알 수 있었다.

 

이런 방법으로는 다음과 같은 반례가 존재함을 알 수 있었다.

 

20 25 60 65의 배열이 주어졌다고 가정해 보자

 

그러면 나의 원래 풀이로는 20+25, 60, 65 이므로 최솟값은 3임을 알 수 있다.

 

그러나, 이 경우 최소값은 2가 나온다.

 

가장 작은 무게와 가장 큰 무게를 더해서 그게 무게 제한보다 작은지 확인해 보자

 

20 + 65 = 85

25 + 60 = 85

 

따라서, 최솟값은 2가 나옴을 알 수 있다.

 

 

 

 

---

 

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        
        
        int idx = 0;
        
        for(int i = people.length-1; idx <= i; i--){
            if(people[i] + people[idx] <= limit){//가장 작은 무게와 가장 큰 무게의 합이 무게 제한을 넘어가는지 확인 
                answer++;
                idx++;
            }else{
                answer++;                
            }
        }
        
        return answer;
    }
}