프로그래머스: 구명보트 최소 개수 계산

문제

무인도에 사람들이 갇혀 있고, 이들을 구명보트를 이용해 구조해야 합니다.
하지만 구명보트는 한 번에 최대 2명까지 탈 수 있고, 무게 제한도 있습니다.

목표는?
가능한 최소한의 구명보트를 사용해서 모든 사람을 구조하는 것입니다.

---

예시

• 사람들의 몸무게: [70, 50, 80, 50]
• 구명보트 무게 제한: 100kg

이때,

• 50 + 50은 함께 탈 수 있음 → 보트 1대
• 70과는 혼자 타야 함 → 보트 1대
• 80도 혼자 타야 함 → 보트 1대

총 3대의 구명보트가 필요합니다.

---

접근 방식(그리디 + 투 포인터)

사람들을 몸무게 기준으로 정렬한 뒤,
가장 가벼운 사람과 가장 무거운 사람을 한 쌍으로 매칭합니다.

무거운 사람부터 하나씩 처리하면서, 가벼운 사람과 같이 탈 수 있으면 같이 태우고, 아니면 혼자 태웁니다.

 

---

JAVA 코드

import java.util.Arrays;

public class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people); // 몸무게 오름차순 정렬

        int left = 0;                  // 가장 가벼운 사람
        int right = people.length - 1; // 가장 무거운 사람
        int boats = 0;

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++; // 두 명이 같이 탈 수 있음
            }
            right--;   // 무거운 사람은 보트에 태움
            boats++;   // 보트 하나 사용
        }

        return boats;
    }
}

 

시간 복잡도

• 정렬: O(N log N)
• 투포인터 루프: O(N)

따라서 전체 시간 복잡도는 O(N log N)으로 효율적입니다.
최대 5만 명까지 문제 없이 처리 가능합니다.