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

---

프로그래머스 Lv2 - 구명보트

프로그래머스에서 그리디 알고리즘으로 분류되어 있는 문제였다.
인자로 받은 people 배열을 무게 오름차순으로 정렬하고 제일 무거운 사람(endIdx)과 제일 가벼운 사람(startIdx)의 무게의 합으로 두 명씩 구조하는게 제일 최적해라고 가정하고 풀이를 진행했다.

주요 로직은 아래와 같다.

1. 사람의 무게가 들어있는 people배열을 오름차순 정렬
2. startIdx가 endIdx를 넘을 때까지 반복문 실행 및 반복문 마지막에 카운트 증가
3. endIdx가 딱 무게 제한일 경우, 한 사람밖에 구명 보트에 태우지 못하니 endIdx를 1 감소시켜 다음 무거운 사람을 제일 무거운 사람으로 지정
4. endIdx가 무게 제한보다 가벼울 경우 startIdx의 무게를 합쳐 비교
5. 합이 무게 제한을 넘을 경우 무거운 사람만 구조(endIdx--)
6. 합이 무게 제한을 넘지 않을 경우는 두명 다 구조

문제 풀이 후 다른 사람의 로직을 확인해 보았는데 대부분 다 나와 비슷한 로직으로 풀이했다. 다만 내 풀이에서 중첩 조건문을 더 단순화해서 풀이할 수 있는데 이 부분이 조금 아쉽다..

Lifeboat.java

package com.example.Programmers.Lv2;

import java.util.Arrays;

/**
 * 프로그래머스 Lv2 - 구명보트
 * 그리디 알고리즘으로 풀이
 * 오름차순 정렬하여 제일 무거운 사람과 제일 가벼운 사람의 무게의 합으로 두 명씩 구조하는게 제일 최적해라고 가정
 */
public class Lifeboat {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int startIdx = 0;
        int endIdx = people.length - 1;

        // 오름차순 정렬
        Arrays.sort(people);

        while (startIdx <= endIdx) {
            // 제일 무거운 사람이 무게 제한을 넘을 경우
            if (people[endIdx] >= limit) {
                endIdx--;
            } else {
                int sum = people[startIdx] + people[endIdx];
                // 제일 무거운 사람과 제일 가벼운 사람의 합이 무게 제한을 넘을 경우 제일 무거운 사람만 구조
                if (sum > limit) {
                    endIdx--;
                    // 제일 무거운 사람과 제일 가벼운 사람의 합이 무게 제한을 넘지 않을 경우 두명 다 구조
                } else {
                    endIdx--;
                    startIdx++;
                }
            }
            answer++;
        }
        return answer;
    }
}

LifeboatTest.java

package com.example.Programmers.Lv2;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class LifeboatTest {
    @Test
    public void testLifeboat() {

        Lifeboat lb = new Lifeboat();

        int[] people1 = { 70, 50, 80, 50 };
        int result1 = lb.solution(people1, 100);

        int[] people2 = { 70, 80, 50 };
        int result2 = lb.solution(people2, 100);

        assertEquals(3, result1);
        assertEquals(3, result2);
    }
}