[프로그래머스] 구명보트 (투 포인터)

문제 소개

구명보트 - 프로그래머스 문제를 정리합니다.
이 문제는 무게 제한이 있는 보트에 사람들을 최소한의 횟수로 태우는 그리디 알고리즘 문제입니다. 핵심은 가벼운 사람과 무거운 사람을 짝지어 최대한 효율적으로 태우는 데 있습니다.

문제 링크: 구명보트 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 몸무게 배열을 오름차순 정렬
2. 가장 무거운 사람부터 보트에 태우되, 가장 가벼운 사람과 같이 탈 수 있는지 확인
3. 두 사람 무게 합이 limit 이하이면 같이 태움, 아니면 무거운 사람만 따로 보냄
4. 양쪽 포인터를 좁혀가며 탐색, 보트를 탈 때마다 카운트 증가

---

해결 과정 및 코드

핵심 아이디어

1. 무거운 사람부터 순서대로 보트에 태우되, 가벼운 사람과 함께 탈 수 있는 경우를 우선 고려
2. 정렬된 배열에서 양쪽 끝을 가리키는 투 포인터 사용
   → left는 가벼운 사람, right는 무거운 사람을 의미
3. people[left] + people[right] <= limit이면 두 사람을 함께 태우고, left와 right 모두 이동
   아니면 right만 줄여서 무거운 사람만 태움

코드

시간 복잡도 : O(N log N)
이유: 정렬 O(N log N) + 투 포인터 탐색 O(N)

 

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);  // 몸무게 오름차순 정렬
        int left = 0;
        int right = people.length - 1;

        while (left < right) {
            // 가장 가벼운 사람과 가장 무거운 사람을 함께 태울 수 있다면
            if (people[left] + people[right] <= limit) {
                left++;  // 가벼운 사람 태움
            }
            // 무거운 사람은 무조건 보트에 태움
            right--;  // 무거운 사람 태움
        }

        // 전체 인원 수 - 짝을 이룬 횟수 = 보트 수
        return people.length - left;
    }
}