[프로그래머스] 구명보트 - Greedy

1. 문제

2. 풀이

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < people.length; i++) {
            list.add(people[i]);
        }

        while (list.size() > 1) {
            if (list.get(0) + list.get(list.size() - 1) <= limit) {
                list.remove(list.size() - 1);
                list.remove(0);
                answer ++;
            } else {
                list.remove(list.size() - 1);
                answer++;
            }
        }
        
        if (list.size() == 1) {
            answer++;
            list.remove(0);
        }
        
        return answer;
    }
}

• 먼저 people을 오름차순 정렬한 후, list에 추가한다. (넣고 빼기 용이하게 하기위해)
• list는 0번째 인덱스가 항상 최소값이며 마지막 요소가 항상 최대값이다.
• 최대값을 하나씩 빼되, 최소값과 비교하여 limit 변수보다 작거나 같을 때, 두개의 원소를 동시에 삭제하며 answer++한다. (하나의 배에 두명을 태운다.)
• 그렇지 않으면 마지막 원소를 하나씩 제거한다.

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