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

문제 설명

 

코딩테스트 연습 - 구명보트

 

접근 방법

해당 문제에서 요구하는 것은 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값입니다. 이때 유의해야할 것은 한 구명보트에 탈 수 있는 사람은 최대 2명뿐이고, 무게 제한이 있다는 점입니다. 즉, 키 포인트(key point)는 최대한 구명보트에는 두 사람씩 태우도록 해야한다는 점입니다.

 

이를 위해 우선 주어진 정수형 배열(people) 오름차순으로 정렬 해줍니다. (내림차순으로 해도 무방합니다.) 이때 무게가 가장 적게 나가는 사람과 무게가 가장 많이 나가는 사람을 태우도록 합니다. 무게가 가장 많이 나가는 사람은 둘이서 타지 못할 '확률'이 제일 높으므로 최대한 무게가 가장 적게 나가는 사람과 태우도록 하는 것입니다.

 

이 둘을 태웠을 때 무게 제한을 초과하지 않는다면 그 다음으로 크고 작은 사람들을 선택하여 앞선 작업들을 반복하도록 합니다. 무게 제한을 초과한다면 무게가 가장 많이 나가는 사람은 혼자 탑승하는 것으로 간주하고 그 다음으로 무게가 많이 나가는 사람을 선택하도록 합니다.

 

이때 무게가 큰 사람들을 선택했는데 그 사람의 무게가 무게 제한의 절반 이하 수치라면 남은 사람들(이 사람보다 무게가 같거나 작은 사람들) 중 누구와도 2인 1조로 탑승할 수 있으며 그 외의 사람들도 마찬가지입니다. 따라서 나머지 사람들의 수를 2인 1조로 구성하여 구명 보트의 개수를 더하고 프로그램을 종료하도록 합니다. (빠른 작업 연산을 위해)

 

 

전체 소스 코드

class Solution {

    public int solution(int[] people, int limit) {
        Arrays.sort(people);

        int countOfBoats = 0, firstIndex = people.length -1, secondIndex = 0;

        while (firstIndex >= secondIndex) {
            if (people[firstIndex] <= limit / 2) {
                countOfBoats += Math.ceil((firstIndex - secondIndex + 1) / 2.0);
                break;
            }

            countOfBoats++;
            if (people[firstIndex] + people[secondIndex] <= limit) {
                secondIndex++;
            }
            firstIndex--;
        }

        return countOfBoats;
    }
}

 

참고자료

• https://programmers.co.kr/learn/courses/30/lessons/42885