[프로그래머스/JAVA] 구명보트

---

- 문제 풀이

 

1.몸무게 배열 정렬

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        // [50, 50, 70, 80]
        // [50, 70, 80]
        Arrays.sort(people);

 

 

 

 

 

 

2. 가장 무거운 사람부터 순회하면서 보트에 태울 수 있는 사람들을 짝지어 태운다.

int index = 0; // 가장 가벼운 사람의 인덱스
        // 무거운 사람 -> 가벼운 사람 순으로 순회
        for(int i = people.length - 1; i >= index; i--) {

 

• 배열의 끝에서부터 시작하여, 가장 무거운 사람부터 순회합니다. i는 가장 무거운 사람의 인덱스를 가리킵니다.
• index가 i보다 작거나 같을 때까지 반복합니다. 이 조건이 만족하지 않으면 모든 사람을 다 태운 것입니다.

 

 

 

 

 

 

3. 가장 가벼운 사람과 가장 무거운 사람을 함께 태울 수 있는지 확인한다.

for(int i = people.length - 1; i >= index; i--) {
            // 가장 가벼운 사람 + 가장 무거운 사람이 limit 보다 작거나 같으면 두사람 묶어서 보트 한개에 태우기
            if(people[index] + people[i] <= limit) {
                answer++;
                index++;
            }else{
                answer++;
            }
        }

 

• people[index] + people[i] <= limit인 경우, 가장 가벼운 사람과 가장 무거운 사람의 무게 합이 보트의 제한 limit을 넘지 않는다는 뜻입니다. 이 경우 두 사람을 함께 보트에 태울 수 있습니다.
• 두 사람을 함께 태웠다면, index++를 통해 가장 가벼운 사람의 인덱스를 다음으로 이동시킵니다.
• 만약 두 사람의 무게 합이 limit을 초과하면, 가장 무거운 사람만 보트에 태웁니다. 이 경우 index를 증가시키지 않고 answer++만 수행합니다.

---

 

예시 실행

사람들의 몸무게가 [70, 50, 80, 50]이고, 보트의 제한이 100인 경우를 생각해봅시다.

1. 정렬 후 배열: [50, 50, 70, 80]
2. i = 3 (80kg), index = 0 (50kg)
   • 50 + 80 > 100이므로, 80kg 한 명만 보트에 태움 (answer = 1)
3. i = 2 (70kg), index = 0 (50kg)
   • 50 + 70 ≤ 100이므로, 50kg과 70kg을 함께 보트에 태움 (answer = 2, index = 1)
4. i = 1 (50kg), index = 1 (50kg)
   • 50 + 50 ≤ 100이므로, 50kg 두 명을 함께 보트에 태움 (answer = 3, index = 2)

결과적으로, 필요한 최소 보트의 수는 3개입니다.

 

---

 

- 정답 코드

// https://school.programmers.co.kr/learn/courses/30/lessons/42885
package Lv2.구명보트;

import java.util.*;

// 정렬 후
// 가장 몸무게가 많이 나가는 사람과 가장 몸무게가 적게 나가는 사람들끼리 보트에 태워 보내기
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        // [50, 50, 70, 80]
        // [50, 70, 80]
        Arrays.sort(people);

        int index = 0; // 가장 가벼운 사람의 인덱스
        // 무거운 사람 -> 가벼운 사람 순으로 순회
        for(int i = people.length - 1; i >= index; i--) {
            // 가장 가벼운 사람 + 가장 무거운 사람이 limit 보다 작거나 같으면 두사람 묶어서 보트 한개에 태우기
            if(people[index] + people[i] <= limit) {
                answer++;
                index++;
            }else{
                answer++;
            }
        }

        return answer;
    }
}