28. LEVEL 2 - 구명보트 - Greedy, Two-Pointer

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

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

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 1;
        int rest = limit;
        int i = 0;	// 가장 가벼운 사람
        int j = people.length - 1;	// 가장 무거운 사람
        
        Arrays.sort(people);	
        
        while(i <= j) {
        	if(rest >= people[i] + people[j]) {
        		rest -= people[i] + people[j];
        		i++;
        		j--;
        	} else if (rest >= people[j]) {
        		rest -= people[j];
        		j--;
        	} else if (rest >= people[i]) {
        		rest -= people[i];
        		i++;
        	} else {
        		answer++;
        		rest = limit;
        	} 	
        }
        
        
        return answer;
    }
}

 

1) 가장 가벼운 사람 + 가장 무거운 사람 2명을 태울 수 있으면 태워본다.

2) 1)이 불가능이면, 무거운 사람을 태운본다.

3) 2)가 불가능이면, 가벼운 사람을 태워본다. 

4) 3)도 불가능하면, 새로운 보트를 구해온다.

 

처음엔, 그냥 가벼운 사람부터 or 무거운 사람부터 차례로 태워보내면 되는줄 알았는데, 아니었음...