프로그래머스 알고리즘 : 구명보트 (LifeBoat)

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

프로그래머스 알고리즘 : 구명보트 (LifeBoat)
 

구명보트 문제를 풀어봤습니다

힌트는 탐욕법(Greedy) 였습니다

방법은 간단합니다 정렬 후 (오름차순)

가장 (큰 값, 가장 작은 값)끼리 더했을 때 LIMIT을 넘긴다면 한 명 밖에 못타니 다음으로 가장 큰 값을 탐색

이런 식 이였습니다 코드를 보시면 더 잘 알 수 있습니다

참고로 정렬은 퀵 정렬을 사용했습니다

class Solution {
   public static int solution(int[] people, int limit) {
        int answer = 0;
        quickSort(people, 0, people.length-1);
        int i = 0;
        int last = people.length -1;
        do {
            if (people[i] + people[last] > limit) {
                last--;
                answer++;
            } else {
                last--;
                i++;
                answer++;
            }
        } while (i <= last);
        return answer;
    }
    static void swap(int[]a, int idx1, int idx2){
        int i = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = i;
    }
    static void quickSort(int[] a, int left, int right){
        int pl = left; // 왼쪽 커서
        int pr = right; // 오른쪽 커서
        int x = a[(pl + pr) /2]; // 피벗
        do {
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                swap(a,pl++,pr--);
            }
        }while (pl <= pr);
        if(left < pr) quickSort(a, left, pr);
        if(pl < right) quickSort(a, pl, right);
    }
}