[P&B] #7 Programmers

프로그래머스 Lv.2 그리디

 

구명보트

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

나의 문제 풀이 코드 (35/100)

import java.util.Arrays;

class Solution {
    public static int solution(int[] people, int limit) {
        int answer = 0;
        int max = 0;
        Arrays.sort(people);

        for (int i = 0; i < people.length; i++) {
            boolean find = false;
            int index = 0;
            for (int j = i + 1; j < people.length; j++) {
                int w = people[i] + people[j];
                if (j == index)
                    break;
                else {
                    if (w <= limit) {
                        max = Math.max(max, w);
                        find = true;
                        index = j;
                    }
                }
            }
            if (find) {
                answer++;
            }
        }
        int result = people.length - (answer * 2) + answer;
        return result;
    }
}

 

답안 참고 후 수정한 코드

#Solution 1
import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int index = 0;
        
        for (int i = people.length - 1; i >= index; i--) {
            if (people[i] + people[index] <= limit) {
                index++;
                answer++;
            }
            else {
                answer++;
            }
        }
        
        return answer;
    }
}

#Solution 2
import java.util.Arrays;
class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1;
        for (; i < j; --j) {
            if (people[i] + people[j] <= limit)
                ++i;
        }
        return people.length - i;
    }
}

 

문제 풀이 코멘트

 다른 사람들이 푼 문제 풀이 방법 중 내가 생각했던 방식으로 구현한 Solution1과 내가 생각하지 못했던 방법인 Solution2가 있어 오늘은 두 가지 풀이방법을 모두 남겨본다. 나는 오름차순 정렬 후 인데스 0부터 끝까지 한번씩 다 더해보며 더해지는 값이 가장 큰 것을 찾아서 그 인덱스를 빼고 다시 또 돌아가서 인덱스 1부터의 합을 구하는 식으로 하려하다보니 빼야하는 인덱스의 값을 제대로 처리하지 못해 중복되는 경우가 발생하여 오류가 생겼다. 즉 이미 짝을 이룬 사람을 고려하지 못했다.

 Solution1에서는 오름차순으로 정렬하지만 시작하는 인덱스를 지정해두고 해당 인덱스에 다른 몸무게를 내림차순으로 더해가며 현재 검사 중인 가장 무거운 사람과 가장 가벼운 사람의 몸무게 합이 구명보트의 limit을 넘지 않는지 확인한다. 계산 후 시작 인덱스를 증가시키는 방법으로 투포인터를 활용한 것 같다. 

 Solution2도 투포인터를 활용한 풀이방법인데 독특하게 경우의 수를 접목시켜 사람 수 - 두 명 태우는 경우의 수 = 한 명 태우는 경우의 수 + 두 명 태우는 경우의 수로 구한 방법이다.

 두 가지 풀이 방법 중 그리디(Greedy) 방법은 두 번째 코드다. 그리디 알고리즘은 각 단계에서 지금 당장 최적인 선택을 하면서 전체적으로 최적의 결과를 얻는 방법을 사용한다. 두 가지 풀이 방법의 시간 복잡도는 모두 O(N log N)이지만 두 번째 코드(그리디 방법)의 경우 한 포인터만을 사용하여 배열을 한 번만 순회하므로, 상수 계수가 작을 가능성이 높다. 따라서 실제 실행 시간 측면에서는 두 번째 코드가 더 빠른 성능을 보일 수 있다.

 결론적으로, 두 가지 풀이 방법은 모두 효율적인 알고리즘이다. 하지만 배열 정렬에 대한 시간 복잡도가 주요하게 영향을 미치므로, 입력으로 주어지는 사람들의 수가 많아질수록 두 번째 코드(그리디 방법)가 약간 더 우세한 경향이 있다.