탐욕법 - 구명보트

프로그래머스 (탐욕법) - 구명보트

해당 문제를 처음 풀때에 3가지 방법을 통해 풀어보려고 했습니다. 3가지 방법중 위에 2가지 방법은 효율성에서는 통과하지 못했고 마지막 방식만 통과하였습니다.
처음에는 정렬 없이 각 무게에 대해 다음 무게와의 합이 limit를 넘지않고 최대인 사람의 경우를 찾는 방식으로 진행했습니다.

public int solution3(int[] people, int limit) {
        int answer = 0;
        int[] peopleWeights = Arrays.copyOf(people, people.length);
        for (int i = 0; i < peopleWeights.length; i++) {
            int weight = peopleWeights[i];
            if (weight > 0) {
                for (int j = i + 1; j < peopleWeights.length; j++) {
                    if (peopleWeights[i] + peopleWeights[j] <= limit) {
                        int preWeight = weight - peopleWeights[i];
                        weight = preWeight > peopleWeights[j] ? weight : peopleWeights[i] + peopleWeights[j];
                        peopleWeights[j] = Math.min(preWeight, peopleWeights[j]);
                    }
                }

                if (weight > 0) {
                    answer++;
                }
            }
        }
        return answer++;
    }

하지만 효율성을 통과하지 못했고, 이유는 무게에 대해 전체 비교를 진행해야 하는것때문에 그런것으로 보입니다.

두번째 방법은 배열을 리스트에 담은 후 정렬을 하고 난 뒤에 두 무게의 합이 처음으로 제한 조건을 넘지 않을때에 두 무게를 리스트에서 제거 하고 그렇지 않을 경우 처음 무게만 제거하는 식으로 코드를 짰습니다.

int answer = 0;
        int[] peopleWeights = Arrays.copyOf(people, people.length);
        List<Integer> peopleList = new ArrayList<>();
        for (int i = 0; i <peopleWeights.length; i++) {
            peopleList.add(peopleWeights[i]);
        }
        peopleList.sort(Comparator.reverseOrder());
        while (!peopleList.isEmpty()) {
            int weight = peopleList.get(0);
            if (weight + peopleList.get(peopleList.size() - 1) <= limit) {
                for (int i = 1; i < peopleList.size(); i++) {
                    if (weight + peopleList.get(i) <= limit) {
                        peopleList.remove(i);
                        break;
                    }
                }
            }
            answer++;
            peopleList.remove(0);
        }
        return answer;

해당 방법의 문제점은 리스트에서 제거할때의 비용을 계산하지 못한점입니다.

마지막 사용한 방법으로는 정렬을 한 배열에서 처음(최소)과 끝(최대) 배열의 값의 합이 limit를 넘지 않았을 경우 가르키는 인덱스를 증가(최소), 감소(최대)를 하고 아닌경우 감소(최대) 만하는 방식으로 로직을 구현했습니다.

public int solution(int[] people, int limit) {
        int answer = 0;
        int[] copiedPeople = Arrays.copyOf(people, people.length);
        Arrays.sort(copiedPeople);

        int minIndex = 0;
        int maxIndex = people.length - 1;

        while (minIndex <= maxIndex) {
            int sum = copiedPeople[minIndex] + copiedPeople[maxIndex];
            if (minIndex != maxIndex && sum <= limit) {
                minIndex++;
            }
            maxIndex--;
            answer++;
        }

        return answer;
    }

해당 방식은 범위가 지속적으로 감소하는 방향으로 구현했고, 리스트를 제거하거나 값의 치환이 아닌 가르키는 인덱스만 변경하여 비용을 최소화 하였기에 효율성 테스트를 통과했습니다.