[프로그래머스,Level 2] 구명보트 (JAVA 구현)

- 첫 풀이

  처음에 문제를 제대로 읽지 않아 보트의 정원이 2명이라는 점을 간과하여, people 배열의 무게를 오름차순으로 정렬한 뒤 가벼운 사람들을 limit까지 태우는 방식으로 풀어보려 했는데 계속 실패가 나왔다. 다른 분들의 풀이를 참고하는 과정에서 첫 문장에 '보트의 정원은 2명'이라는 강조 표시를 보고 깨달았다. (생각 외로 이를 놓치는 사람이 많은 것 같다.)

 

- 정답풀이

  결국 인원 제한이 2명인 보트를 그리디스럽게 채우기 위해서는, 가장 많은 무게가 나가는 사람과 함께 가장 적은 무게가 나가는 사람을 태우는 것이 최적일 것이다. 

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        // l_idx: 가장 무게가 적은 사람을 가리키는 인덱스, r_idx: 가장 무게가 많은 사람을 가리키는 인덱스
        int l_idx =0;
        int r_idx = people.length-1;
        
        // 1. 배열 정렬.
        Arrays.sort(people);
        
        // 2. l_idx가 r_idx보다 왼쪽에 있는 동안 반복.
        for(int i=l_idx;i<=r_idx;){
            // 3. 가장 무게가 많은 사람 + 가장 무게가 적은 사람 <= 무게제한인 경우, 보트 출발, 인덱스 변경.
            if(people[i] + people[r_idx]<=limit) {
                answer++;
                i++;
                r_idx--;
            // 4. 나머진 무거운 사람 먼저 출발.                
            }else{
                answer++;
                r_idx--;
            }
        }        
        
        return answer;
    }
}