[프로그래머스/Programmers] 구명보트 (Java - Greedy - Lv2)

구명보트

 

프로그래머스

---

⭐️ 코드

import java.util.Arrays;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);

        int j = 0;
        for (int i = people.length-1; i>=j; i--) {
            if (people[j] + people[i] <= limit) {
                j++;
            }
            answer++;
        }

        return answer;
    }

}

---

💡 문제 풀이

이 문제는 그냥 그리디(탐욕법 - Greedy)으로 풀라고 명시를 해뒀다. 그래서 쉽게 알고리즘에 접근 할 수 있었다.

 

그리디 알고리즘은 뭔가 완전탐색과 비슷한 느낌이 들긴 한다. 하지만 매 선택에서 최선의 선택을 한다는 것이 완전 탐색과 다른 부분이라고 생각된다. 정확하게는 어떤 알고리즘이고, 무슨 방식으로 진행되는지는 잘 모르겠다. 이 부분은 다음 알고리즘 강의 시간에 제대로 배워보도록 하겠다!!

 

Greedy 알고리즘 (탐욕법)

자세하게 궁금하다면 아래 블로그를 참고하자!

알고리즘 - 그리디 알고리즘(Greedy Algorithm)

 

일단 먼저 Arrays.sort(people)를 통해 오름차순으로 정렬해준다. (내림차순도 상관 없다)

나는 오름차순으로 정렬했기 때문에 오름차순 기준으로 설명하겠다.

int j = 0;
for (int i = people.length-1; i>=j; i--) {
    if (people[j] + people[i] <= limit) {
        j++;
    }
    answer++;
}

시작은 가장 뒤의 사람과, 가장 앞의 사람의 몸무게를 더했을 때 그 값이 limit 보다 같거나 작으면 그 둘은 한 배를 탈 수 있다.

따라서 가장 앞의 사람을 가리키는 j를 하나 올려주게 된다. 

 

하지만 두 사람의 몸무게가 limit보다 크다면 가장 뒤의(가장 몸무게가 무거운)사람은 혼자 배를 타야하기 때문에 answer++를 통해 보트 개수를 하나 늘려준다.

그 후 j는 그대로이기 때문에 다음 사람과 또 더해서 limit 비교를 하게 된다. 이렇게 되면 최소한의 배의 숫자로 모두를 옮길 수 있다.

---

👀 후기

쓸데없이 질문하기 눌러서 다른거 봤더니 더 헷갈리게 됐다... 

생각보다 안어려운데 난 왜이렇게 고생을 했던 것인가..

화가난다..!!!!