구명보트 :그리디 (Level2)

이번문제는 구현하기는 쉬우나, 방법을 생각해내는것이 어렵다고 생각합니다.

 

여러가지 방식을 정해보았으나, 결국 명확한 해법을 찾지못해 다른 사람들의 방식을 확인 후 구현하였습니다.

 

풀이법은 단순합니다.

1. 사람들을 오름차순으로 정렬한 후

2. 최대 2명만 태울 수 있으니, 가장 작은사람 + 가장 큰사람 <= limit를 판단하여,

태울 수 있다면 front index를 다음 작은 사람으로, back index를 다음 큰사람으로 이동한다. (둘다 태울 수 있기 때문에)

태울 수 없다면, back index만 다음 큰사람으로 이동한다. (큰 사람만 태울 수 있기 때문에)

 

((front: 50), 50, 70, (back:80)) =====> answer++

---> ((front:50), 50, (back:70), 80) =====> answer++

---> ((front:50), (back:50), 70, 80) =====> answer++

 

((front: 50), 70, (back:80)) =====> answer++

---> ((front:50), (back:70), 80) =====> answer++

---> ((front:50), (back:70), 80) =====> answer++

 

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people); // 오름차순 정렬
        
        int front = 0;
        int back = people.length-1;
        
        while(front <= back){ 
            answer++; // 구명보트 수
            
            // 최대 2명밖에 못태움
            if(people[front] + people[back] <= limit){ // 둘다 태울 수 있다면, (front 하나 증가 + back하나 감소)
                front++;
            }
            back--; // 둘다 못태운다면, 큰 놈만 태우기 (back하나 감소)
        }
        return answer;
    }
}