[Java 자바] 프로그래머스 > Lv.2 구명보트

https://programmers.co.kr/learn/courses/30/lessons/42885?language=java

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

문제 설명

• 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
• 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
• 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
• 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

---

 

풀이 방법

 

구명 보트는 최대 2명씩밖에 탈 수 없으니 배열을 정렬하여 가장 적은 몸무게인 사람 + 가장 큰 몸무게인 사람을 비교하여 경우의 수를 계산한다.

 

1. 배열 정렬하기

2. 오름차순으로 정렬된 배열을 마지막 원소부터 idx보다 크거나 작을때까지 반복문을 돌린다.

• 만약 몸무게가 가장 많이 나가는 사람의 몸무게와 적게 나가는 사람의 몸무게 합이 limit을 넘지 않을때,
• answer에 1을 더한 후 idx값을 1 증가시킨다. =>  idx는 몸무게가 작은 사람의 위치를 나타내는 변수이다.
• 만약 합이 limit을 넘을때 answer에 1을 증가시킨다.

 

예를 들어 [10,30,40,80,90] 배열과 limit=100일 때,

1. people[0](10) + people[4](90) =100 <= limit 이므로 idx++,answer++ => idx=1,answer=1,

2. people[1](30) + people[3](80) =110 >=limit 이므로 answer++ => answer=2

3. people[1](30) + people[2](40) =70 <=limit 이므로 idx++,answer++ => idx=2,answer=3

 

 

전체 코드

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