[프로그래머스] (Java) 구명보트 (그리디/Greedy)

 

 

📑 1. 문제설명

---

💡 2. 접근방식

 
문제 제한조건
1. 한 번에 최대 두명까지 보트에 태울 수 있음
2. 몸무게 합이 `limit` 이하여야 함
 
따라서 최소보트를 사용하는 전략을 짜려면 
배열을 정렬하여 가장 가벼운 사람 + 가장 무거운 사람 조합을 짝지어야 함.
가장 큰 몸무게를 가진 사람을 최대한 빨리 처리하면서도 보트 사용을 줄일 가능성이 높기 때문이다.

만약 두 사람의 몸무게 합이 limit 이하라면, 한 보트에 태울 수 있다. 
합이 limit을 초과한다면, 무거운 사람을 반드시 한 명만 보트에 태워야 한다.
이렇게 하는 것이 남은 사람들을 효율적으로 처리하기 위한 최선의 선택이다. 

---

⭐ 3. 정답코드

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        
        // idx 는 가장 가벼운 사람의 인덱스
        // i 는 가장 무거운 사람의 인덱스
        int idx = 0;
        for(int i = people.length-1; i>=idx; i--) {
            if(people[i]+people[idx]<=limit) {
                answer++;
                idx++;
            } else  answer++;
        }
        return answer;
    }
}

1. 오름차순으로 배열 정렬하기
2. 마지막 요소부터 idx보다 크거나 작을때까지 반복문을 돌린다.

• 마지막요소 = 몸무게가 가장 많이 나가는 사람
• idx = 몸무게가 가장 가벼운 사람

3. 만약 몸무게가 가장 많이 나가는 사람의 몸무게와 적게 나가는 사람의 몸무게 합이 limit을 넘지 않는다면
answer에 1 증가 후 idx값도 1 증가시킨다. =>  idx는 몸무게가 작은 사람의 위치를 나타내는 변수이다.

3. 몸무게가 가장 많이 나가는 사람의 몸무게와 적게 나가는 사람의 몸무게 합이 limit을 넘을 때는?

가장 무거운 사람만 보트를 사용해야 한다.  즉, 합이 limit을 넘으면 가장 가벼운 사람(idx)은 보트에 함께 탈 수 없기 때문에 따라서, 가장 무거운 사람(i)은 단독으로 보트를 타야 하므로 answer를 1 증가한다. 

가장 무거운 사람은 이미  보트를 탔으므로 i--를 통해 가장 무거운 사람을 처리하고(위치 감소(, 그다음으로 무거운 사람을 대상으로 진행한다.  
반면 가장 가벼운 사람의 위치(idx)는 변화가 없다. 왜냐하면  limit을 초과했기 때문에 가장 가벼운 사람은 아직 처리되지 않았기 때문에  idx는 그대로 유지되고, 다음 반복에서 다시 가장 가벼운 사람과 새로운 가장 무거운 사람을 비교해 준다.
 

👏🏻 좋아요 가장 많이 받은 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1;
        for (; i < j; --j) {
            if (people[i] + people[j] <= limit)
                ++i;
        }
        return people.length - i;
    }
}

 사람 수 - 두 명 태우는 경우의 수 = 한 명 태우는 경우의 수 + 두 명 태우는 경우의 수
 사람 수 = 초과하는 사람들 구명보트 수 + 짝지어 타는 사람들 구명보트 수 * 2

---

🐦 4. 같은 유형 문제

[프로그래머스] (Java) 체육복 (그리디/Greedy)

[프로그래머스] (Java) 조이스틱 (그리디)

[프로그래머스] (Java) 큰 수 만들기 (그리디/Greedy)

[프로그래머스] (Java) 단속카메라 (그리디/Greedy)