Level2 구명보트 ( 탐욕법 Greedy )

 

🤔어떻게 하면 효율 적으로 태울지

limit이 100 이고 (제한인원 2명) 10 20 60 80 (정렬하고) 의 몸무게를 가진 손님이 있으면 어떻게 하면 딱 100kg에 딱 맞춰 태울까를 고민했었다. 하지만 생각을 해 보다 최소 보트의 수를 구하는 문제이기에 (10 80) 먼저 하나 ( 20 80 ) 을하나 똑같다. 그 이유는 정렬이 되어있고 + (제한인원이 2명이고) 탐욕적으로 최대 큰 수인 80에서 10을 선택하지 않으면 그 밑에 수는 80보다 작기에 100까지 최대 값을 설정할 수 없기 떄문이다.

그렇기에 탐욕적으로 큰사람 한명을 태우고 작은사람 한명이 가능하면 2명을 태워 나가고 

불가능 하다면 1명을 태워 나간다.

 

⭐투포인터알고리즘⭐

public static int solution(int[] people, int limit) {
    int answer = 0;

    Arrays.sort(people); // 몸무게 별로 정렬 

    int lt = 0; // 작은 몸무게 
    int rt = people.length-1; // 큰 몸무게 
    while(lt<=rt){
        // if문에 걸리면 2명이 나가고 아니면 1명이 나간다.
        if(people[lt]+people[rt--]<=limit) lt++;
        answer++; // 보트수 ++
    }
    return answer;
}