[Programmers]-구명보트

문제

우리가 아는 무인도에서 최소 몇개 구명보트를 써서 탈출하면 되는 문제이다. 여기서 조건은 최소 무게가 있다. 또 한번에 최대 2명씩 탄다. 문자열배열(people)에 사람들 무게를 받는다. limit는 구명보트의 무게 제한이다. 최소 몇개의 구명보트 개수가 필요한지 반환하면 되는문제이다.

코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        for(int a : people) list.add(a);
        
        while(list.size() > 1){
            
            if(list.get(0)+list.get(list.size()-1) <= limit)
                list.remove(0);
            list.remove(list.size()-1);
            answer++;
        }

        return list.size()==1 ? ++answer : answer;
    }
}

코드 설명

처음에 정렬은 한뒤 앞에서부터 차례대로 내보내려고했는데

이렇게되면 무게가 낮은사람들 먼저 내보내면서 보트를 더 써야된다. 그래서 가벼운사람과 무거운사람을 묶어 내보내는게 가장 최소값으로 내보낼 수 있다.

요약

• 그리디알고리즘이다.
• 갈수록 뭔가 어려워지는것 같다.