[프로그래머스] 구명보트 - Java

• 문제

풀이과정

1. 주어진 사람들의 무게를 정렬한다.
2. 현재 남아있는 사람들 중 가장 무거운 사람(주어진 배열의 가장 뒤쪽 index부터 센다)과 가장 가벼운 사람의 무게(주어진 배열의 가장 앞 index부터 센다)의 합이 무게 제한을 초과하면 가장 무거운 사람이 혼자서 보트를 타야 한다.
   • 배열 뒤에서부터 세는 index 값 1 감소
3. 2번의 계산에서 무게 제한을 초과하지 않을 경우 가장 무거운 사람과 가장 가벼운 사람이 함께 구명 보트에 탑승한다.
   • 배열 뒤에서부터 세는 index 값 1 감소
   • 배열 앞에서부터 세는 index 값 1 증가
4. 무거운 사람의 순서를 나타내는 index 값이 가벼운 사람을 나타내는 index 값보다 큰 동안 2~3번 과정을 반복한다. 반복이 종료되었을 때 두 index가 같다면 마지막 한 사람이 남은 것이므로 추가적으로 보트가 한 대 더 필요하다.

• 문제는 정답으로 처리되었지만, 이게 Greedy가 맞는지 약간의 의문이 든다.
  나는 Greedy algorithm을 부분 문제의 최적해의 집합이 결국 전체 문제의 최적해(또는 그에 매우 가까운 해)가 되는 것을 기대하는 풀이방식이라고 이해하고 있는데, 아래의 풀이 코드가 과연 부분 문제의 최적해를 취하고 있는가에 대해 의문부호가 남기 때문이다.
  아무래도 문제의 제한조건으로 한 번에 최대 2명으로 탑승 인원 제한이 고정되어 이러한 생각이 드는 것 같다. 구명보트별로 탑승 가능 인원과 무게 제한이 별도로 존재했다면 좀 더 재밌는 문제가 되지 않았을까?

Code

import java.util.Arrays;

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

        int heavyIdx = people.length - 1;
        int lightIdx = 0;

        while (heavyIdx > lightIdx) {
            int heaviestPerson = people[heavyIdx];
            int lightestPerson = people[lightIdx];

            if (heaviestPerson + lightestPerson > limit) {
                // 가장 무거운 사람 한 명이 보트 하나를 차지
                heavyIdx--;
            } else {
                // 현재 남아있는 사람들 중 가장 무거운 사람과 가장 가벼운 사람이 같이 보트 탑승 가능
                heavyIdx--;
                lightIdx++;
            }

            boatCount++;
        }

        // 마지막 한 사람이 남아있는 경우
        if (heavyIdx == lightIdx) {
            boatCount++;
        }

        return boatCount;
    }
}

결과