[프로그래머스 Lv.2] 구명보트

풀이 날짜 : 2025.05.07
문제 유형 : 탐욕법
문제 제목 : 구명보트
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42885

Intuition

• 각 사람의 몸무게(people)와 구명보트의 무게 제한(limit)이 주어질 때 필요한 최소한의 구명보트 개수를 구해야 한다.
• 1개의 보트에는 최대 2명까지만 태울 수 있다는 조건이 있다.
  • 2명을 태운 보드가 많을수록 필요한 보트 개수는 줄어든다.
  • 가장 무거운 사람을 가능한 한 가볍고 조건을 만족하는 사람과 짝짓는 것이 최적이다. ⇒ 그리디 방식
  • 무거운 사람은 짝지을 수 있는 대상이 적고 혼자 탈 가능성이 높다. 즉, 무게 제한을 넘어가면 무거운 사람이 혼자 타야 한다.
• 배열을 정렬 후 양끝에서 최댓값, 최솟값을 결정할 수 있다.
  • 양끝에서 시작하여 조건을 만족하는 조합을 찾는 경우 투 포인터 기법을 사용할 수 있다.

Approach

• 사람들의 몸무게를 담은 배열(people)을 오름차순으로 정렬한다.
• 필요한 보트 개수(boat), 왼쪽 포인터(start), 오른쪽 포인터(end)를 선언한다.
• start와 end가 만날 때까지 탐색을 반복한다.
  • start와 end의 몸무게 합이 limit 보다 크면, 무거운 사람을 혼자 태워야 하므로 end를 1 증가시킨다.
  • start와 end의 몸무게 합이 limit 보다 작거나 같으면, 같이 탈 수 있으므로 start를 1 증가, end를 1 감소시킨다.
  • 한 번의 탐색 종료 후 boat를 1 증가시킨다.
    (두 포인터가 만나면 1명 남아있다는 뜻으로, 마찬가지로 boat를 1 증가시키면 된다.)
• boat를 반환한다.

Complexity

• Time complexity : O(n log n)
  • people의 길이를 n 이라고 할 때,
    오름차순 정렬에서 O(n log n)
    투 포인터 탐색에서 start, end 합쳐서 최대 n번 이동하면 while 루프가 끝나므로 O(n)
    종합적으로 O(n log n)이다.
• Splace complexity : O(1)
  • 입력 배열 외에 추가 메모리 사용 거의 없음

Code (JS)

function solution(people, limit) {
    // 오름차순 정렬
    people.sort((a, b) => a - b);

    let boat = 0;
    let start = 0;
    let end = people.length - 1;

    // 양끝에서 탐색
    while (start <= end) {
        if (people[start] + people[end] > limit) {
            // 무거운 사람 혼자 탐
            end -= 1;
        } else {
            // 무거운 사람, 가벼운 사람 같이 탐
            start += 1;
            end -= 1;
        }

        boat += 1;
    }

    return boat;
}