[알고리즘]프로그래머스 42885번 - 구명보트

프로그래머스 42885번 - 구명보트

프로그래머스 42885번 - https://programmers.co.kr/learn/courses/30/lessons/42885

 

요구사항

1. 구명보트는 한 번에 최대 2명씩 탈 수 있고, 무게 제한도 있습니다.

2. 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 반환하라.

 

요구사항 분석 및  풀이과정

1. 직관적으로 생각해보자. 구명보트를 최소한으로 필요하려면 가장 무거운 사람부터 태워 보내야 제한된 무게의 구명보트에 최대 2명을 태울 수 있을 것 같다. 무게 순으로 사람들을 정렬하자.

2. 가장 무거운 사람을 태운다고 하면, 최대 2명을 태울 수 있기 때문에 남은 자리에 태울 수 있는 사람을 찾아본다.

3-1. 가능성이 높은 사람은 가장 무게가 작은 사람일 것이며 그 사람의 무게와 가장 무거운 사람의 무게가 구명보트의 제한을 넘지 않는지를 확인한다.

3-2. 제한을 넘는 다면, 이미 가장 무게가 적은 사람이 타기로 했으니, 가장 무거운 사람은 누구와도 함께 탈 수 없다는 의미이고 혼자 보내야 한다. 

3-3. 제한을 넘지 않는다면 두 명을 태워서 보낸다.

4. 그런 후 1번부터 동일한 작업을 반복한다.

 

여기서 중요한 점은 가장 무게가 작은 사람보다 바로 무게가 작은 사람이 탈 수도 있을 수 있지 않나, 왜 굳이 제한을 넘지 않는 한에서 최소한의 무게를 따지는 거지라고 생각할 수 있다.

 

하지만 우리한테 중요한 것은 누가 타느냐가 아니라 제한을 넘기지 않고 두 명이 탈 수 있냐 없냐이다.  구명보트의 제한보다 작으면 누가 타던지 우리가 알빠가 아니라는 말이다.

 

물론, 무게 제한에 맞게 다른 방법으로 태워도 된다. 하지만 구현이 귀찮아질 것이다. 순차적으로 처리하는 것이 아니라 비순차적으로 처리를 하여야할 것이기 때문이다.

 

소스코드 작성

import java.util.Arrays;

class Solution {

    public int solution(int[] people, int limit) {
        int result = 0;
        
        Arrays.sort(people);
        int left = 0, right = people.length - 1;
        
        while(left < right) {
            if (people[left] + people[right] <= limit) {
                left++;
                right--;
            } else {
                right--;
            }
            result++;
        }
        
        return left == right ? result + 1 : result;
    }
}

 

결과

 

소스코드 깃허브 주소

링크