[프로그래머스] JavaScript Lv2 - 구명보트(42885)

개요

문제 이름: 구명보트 (42885)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42885
플랫폼: 프로그래머스
알고리즘 분류: 탐욕법(Greedy)
소요 시간: 5시간

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 구명보트를 최소한으로 사용하여 모든 사람을 구출하는 최적의 방법을 찾는 것입니다. 문제의 핵심은 다음과 같습니다.

• 구명보트는 최대 2명까지 탈 수 있습니다.
• 구명보트에는 무게 제한이 있습니다.
• 최소한의 구명보트로 모든 사람을 구출해야 합니다.

이 문제는 그리디(Greedy) 알고리즘을 사용하여 효율적으로 해결할 수 있습니다. 그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 방식으로, 이 경우 가장 무거운 사람과 가장 가벼운 사람을 함께 태워 보내는 전략을 사용합니다.

• 사람들의 몸무게를 오름차순으로 정렬합니다.
• 가장 가벼운 사람(left)과 가장 무거운 사람(right)을 선택합니다.
• 두 사람의 무게 합이 제한 무게 이하라면 함께 보트에 태웁니다.
• 그렇지 않다면 무거운 사람만 보트에 태웁니다.
• 이 과정을 모든 사람이 구출될 때까지 반복합니다.

문제 접근 방식은 위와 같습니다.

 

시도

1차 시도 (실패) - DP

function solution(people, limit) {
    people.sort((a, b) => a - b);
    const n = people.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        for (let j = 1; j < i; j++) {
            if (people[i - 1] + people[j - 1] <= limit) {
                dp[i] = Math.min(dp[i], dp[j - 1] + (i - j + 1) / 2);
            } else {
                break;
            }
        }
    }

    return Math.ceil(dp[n]);
}

이 접근 방식은 동적 프로그래밍(DP)을 사용하여 문제를 해결하려고 시도했습니다. 하지만 이 방법은 효율성 측면에서 실패했습니다.

• 사람들의 몸무게를 오름차순으로 정렬합니다.
• dp 배열을 생성하여 각 인덱스에서의 최소 보트 수를 저장합니다.
• 이중 반복문을 사용하여 모든 가능한 조합을 확인합니다.
• 두 사람의 무게 합이 제한 이하일 때, 최소 보트 수를 갱신합니다.

시간 복잡도: O(n^2), 여기서 n은 사람의 수입니다.
공간 복잡도: O(n), dp 배열의 크기입니다.

 

이 접근 방식은 모든 조합을 고려하기 때문에 시간 복잡도가 높아 효율성 테스트를 통과하지 못했습니다.

 

2차 시도 (성공) - 그리디

function solution(people, limit) {
    var answer = 0;  // 필요한 구명보트의 수
    var left = 0,  // 가장 가벼운 사람의 인덱스
        right = people.length - 1;  // 가장 무거운 사람의 인덱스
    
    // 사람들의 몸무게를 오름차순으로 정렬
    people.sort((a, b) => a - b);
    
    // 가장 가벼운 사람과 가장 무거운 사람부터 시작하여 중앙으로 이동
    while (left <= right) {
        // 가장 가벼운 사람과 가장 무거운 사람을 한 보트에 태울 수 있는 경우
        if (people[left] + people[right] <= limit) {
            left++;  // 가장 가벼운 사람을 태웠으므로 다음 사람으로 이동
        }
        // 무거운 사람은 항상 보트에 타게 됨
        right--;  // 다음 무거운 사람으로 이동
        answer++;  // 보트 수 증가
    }
    
    return answer;  // 필요한 총 보트 수 반환
}

이 접근 방식은 그리디 알고리즘을 사용하여 문제를 해결합니다.

• 사람들의 몸무게를 오름차순으로 정렬합니다.
• 두 포인터(left, right)를 사용하여 가장 가벼운 사람과 가장 무거운 사람을 선택합니다.
• 두 사람의 무게 합이 제한 이하라면 함께 보트에 태웁니다(left++ 와 right--).
• 그렇지 않다면 무거운 사람만 보트에 태웁니다(right--).
• 각 단계마다 보트 수(answer)를 증가시킵니다.
• 모든 사람이 처리될 때까지(left > right) 반복합니다.

시간 복잡도: O(n log n), 정렬에 의해 결정됩니다.
공간 복잡도: O(1), 추가 공간을 사용하지 않습니다.

 

이 방법은 각 단계에서 최적의 선택을 하므로 효율적이며, 모든 테스트 케이스를 통과합니다.

 

사용된 메서드

• sort((a, b) => a - b): 배열을 오름차순으로 정렬합니다. 콜백 함수 (a, b) => a - b는 비교 함수로, a가 b보다 작으면 음를, 같으면 0을, 크면 양수를 반환합니다.
• Math.ceil(): 주어진 숫자보다 크거나 같은 최소 정수를 반환합니다.