[PGM] 구명보트 (java)

문제링크

https://programmers.co.kr/learn/courses/30/lessons/42885

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 Greedy

1. 문제 이해

구명보트를 활용하여 무인도에 갖힌 사람들을 구출할 때 구명보트를 최소한으로 사용한다면 몇개의 구명보트면 구할 수 있을지를 구하는 문제이다. 이 때 구명보트에는 최대 2명의 사람과 제한무게 이하로 탑승할 수 있다.

 

2. 접근방법

Greedy한 접근을 하면 문제를 해결할 수 있다.

사람들의 무게를 정렬하여 최고 무게를 보유한 사람과 최고로 적게 무게가 나가는 사람을 묶어서 탑승하여주면된다. 이 때 무거운 사람이 너무 무거운 경우에는 혼자 탑승시킨다면 그리디로 문제를 해결할 수 있다.

구현코드

package pgm_42885;

import java.util.Arrays;

public class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);

        int bigPeople = people.length-1;
        int smallPeople = 0;

        int boatCount = 0;
        while (bigPeople >= smallPeople){
            boatCount++;
            if(people[smallPeople] + people[bigPeople] <= limit){
                smallPeople++;
            }
            bigPeople--;
        }
        return boatCount;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)