[Java][프로그래머스] 구명 보트 - 그리디

구명 보트 - Level 2

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        
        int n = people.length;
        
        int left = 0;
        int right = people.length - 1;
        
        while(left <= right){
            if(people[left] + people[right] <= limit){
                left++;
            }
            right--;
            answer++;
        }
        
        return answer;
    }
}

푼 방법

• 오름차순으로 정렬을 한다.
• left, right로 각각 한명씩 선택하고, 만족을 못하면 이동하는 방식으로 한다.
• left 인덱스가 right보다 커지면 종료하므로 전체를 다 돌게 된다.
• 가장 가벼운 사람 선택하고, 가장 무거운 사람과 합쳐서 limit보다 작거난 같으면 선택하고 아니면 옆으로 이동한다.

20 30 70 80 이런식으로 있다고 가정한다. limit은 100이다.

20을 선택하면 80과 같이 태워야 가장 효율적이다. 그러므로 20을 선택하면 80을 선택하도록 설계해야 한다.
그래서 가장 가벼운 사람을 고르고, 그 사람과 가장 무거운 사람을 비교하고 초과하면 두번째로 무거운 사람과 비교하는 식으로 했다.
가벼운 사람을 고르는 건 오름차순이므로 left, 무거운 사람을 고르는 건 오른쪽이므로 right로 해서 left는 둘을 태우게 되면 이동하는 식으로, 가벼운 사람 기준으로 같이 태울 사람을 정하는 식으로 했다.

회고

• 처음에 아이디어 자체는 빨리 떠올렸던 것 같다. 가벼운 사람 한명 태우고, 가장 무거운 사람을 내림차순으로 검사하는 방식으로..
• 처음이 이중 for문으로 돌아가면서 선택해야 하나 싶었는데 생각해보니 모두 돌 필요가 없고 두명을 고르는 것이기 때문에 반씩 돌면 되니까, 두 변수를 두고 아니면 이동하는 식으로 구현했다. 근데 이 방식을 생각하는게 조금 걸렸다.