[알고리즘] 프로그래머스 - 구명보트(Greedy)

1. 조건

---

2. 내 생각

---

배열이 [1, 2, 3, 4] 이렇게 있다면 각각의 인덱스는 0, 1, 2, 3이 된다. 인덱스 0,1 0,2 0,3 1,2 1,3 2,3을 비교해 값을 추려가면 될 것 같았다. 배열의 값을 차례대로 비교하기위해 내림차순 또는 오름차순 정렬을 해주면 더 빠를 것이다.

3. 실행 결과

---

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0;
        int right = people.length-1;
        int count = 0;

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
                right--;
            } else {
                right--;
            }
            count++;
        }

        return count;
    }
}

처음의 두 인덱스부터 시작하여 하나씩 늘려가는 것도 방법일 수 있지만 내가 선택한 방법은 인덱스의 처음(0)과 끝(배열길이-1)을 정해주었고 반복문을 돌며 두 값의 합이 limit을 넘는지에대한 비교를 진행하고 두 값의 거리를 좁혀가며 필요한 구명보트의 수(count)를 하나씩 늘려갔다.

---

(Greedy Algorithm) 탐욕법

여러 경우에서 결정해야 할 때 최적이라고 생각되는 것 하나를 선택하는 방식으로 최종 결과에 도달하는 것이다. 위의 문제에서 그리디 알고리즘이 적용된 방법으로는 아래와 같다.

1. 사람들의 몸무게를 오름차순으로 정렬.
2. 가장 가벼운 사람과 가장 무거운 사람을 선택.
3. 선택한 두 사람의 몸무게 합을 구명보트의 무게 제한과 비교.
4. 합이 무게 제한 이하 -> 두 사람을 같이 태우고 다음으로 넘어간다.
5. 합이 무게 제한 초과 -> 무거운 사람은 혼자 태우고 다음으로 넘어간다.
6. 태운 인원은 제외, 다음 사람 선택.
7. 모든 사람들을 대상으로 반복 진행.
8. 구명보트의 개수를 반환합니다.