구명보트

문제

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 구하는 프로그램을 작성하는 문제입니다.

• 입력: 사람들의 몸무게 배열 people (길이 1 이상 50,000 이하, 몸무게는 40 이상 240 이하), 구명보트의 무게 제한 limit (40 이상 240 이하)
• 출력: 필요한 구명보트의 최솟값

링크: https://school.programmers.co.kr/learn/courses/30/lessons/42885

풀이: 정렬과 투 포인터를 활용한 탐욕법(Greedy)

구명보트를 최대한 적게 사용하려면, 가장 무거운 사람과 가장 가벼운 사람을 짝지어 태우는 것이 최적의 전략입니다. 만약 가장 무거운 사람과 가장 가벼운 사람의 합이 무게 제한을 초과한다면, 그 무거운 사람은 다른 누구와도 같이 탈 수 없으므로 무조건 혼자 타야 합니다.

• 오름차순 정렬: 사람들의 몸무게 배열 people을 오름차순으로 정렬합니다. 이를 통해 가장 가벼운 사람은 맨 앞(l)에, 가장 무거운 사람은 맨 뒤(r)에 위치하게 됩니다.
• 투 포인터 탐색: 왼쪽 포인터 l은 0부터 시작하고, 오른쪽 포인터 r은 배열의 끝(people.length - 1)에서 시작하여 두 포인터가 엇갈릴 때까지(l <= r) 반복합니다.
• 조건 판별 및 보트 탑승:
  • people[r] + people[l] <= limit: 가장 무거운 사람과 가장 가벼운 사람이 함께 탈 수 있는 경우입니다. 가벼운 사람도 보트에 탔으므로 왼쪽 포인터를 한 칸 뒤로 이동시킵니다. (l++)
  • 위 조건의 만족 여부와 상관없이, 가장 무거운 사람(r)은 무조건 이번 보트를 타고 나가야 합니다. 따라서 오른쪽 포인터는 매 반복마다 한 칸씩 앞으로 이동합니다. (r--)
  • 보트 한 대가 출발했으므로 정답 카운트를 1 증가시킵니다. (ans++)

코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        // 1. 몸무게를 오름차순으로 정렬
        Arrays.sort(people);
        
        int l = 0, r = people.length - 1;
        int ans = 0;
        
        // 2. 투 포인터를 사용하여 가장 가벼운 사람과 가장 무거운 사람 매칭
        while (l <= r) {
            // 두 사람의 무게 합이 제한 이하이면 가장 가벼운 사람도 같이 탑승
            if (people[r] + people[l] <= limit) {
                l++;
            } 
            
            // 무거운 사람은 조건에 상관없이 무조건 탑승
            r--;
            
            // 보트 1대 사용
            ans++;
        }
        
        return ans;
    }
}

알고리즘 분류

탐욕법 (Greedy), 정렬 (Sorting), 투 포인터 (Two Pointers)