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

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

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

프로그래머스

---

접근

limit가 100일 때 다음과 같은 테스트 케이스를 가정한다.

[40, 70, 20, 50]

 

-> 제일 가벼운 애들부터 태우는 경우

20 + 40 < 100 -> answer++
50 + 70 > 100 -> answer+= 2

이런 방식으로는 3개의 구명보트가 필요하다. 50인 친구에 대한 구명보트와 70인 친구에 대한 구명보트가 각각 필요하기 때문이다.

 

-> 제일 가벼운 애 + 제일 무거운 애 세트로 태우는 경우

20 + 70 < 100 -> answer++
40 + 50 < 100 -> answer++

이런 방식으로는 2개의 구명보트가 필요하다.

 

구명보트를 가장 적게 쓰는 방법은 제일 가벼운 애 + 제일 무거운 애 세트로 태우는 경우가 되겠다.

 

따라서 주어진 people 배열을 오름차순 한 다음, 맨 앞 인덱스와 맨 뒤 인덱스를 고르는 방식을 적용할 수 있다.

오름차순된 people 배열

20 + 70은 100을 초과하지 않으므로 answer++을 하고 두 인덱스는 각각 오른쪽, 왼쪽으로 이동시키면 된다.

 

그런데 만약 두 인덱스 합이 limit를 초과하는 경우는 어떻게 해야할까? (limit가 80인 경우를 생각해보자)

이럴 경우 뒤에 있는 친구가 원인이기 때문에 이 친구만 따로 구명보트를 타고 떠나야 한다.

70인 친구를 가리키는 인덱스만 이동시키고, 아직 떠나지 못한 친구에 대한 인덱스는 다른 친구와 탈 수 있는지 확인해야 하기 때문에 고정시킨다.

두 인덱스가 일치해질 때까지 반복문을 순회한다.

인덱스가 일치하므로 같은 값을 두 번 더하고 limit를 초과하는지 여부를 계산할텐데, 어차피 결과가 어떻게 됐든 answer++이 되도록 처리가 된다.

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int min = 0;
        
        for (int i = people.length - 1; i >= min; i--) {
            if (people[i] + people[min] <= limit) { // 둘 다 구명보트를 탑승하므로 두 인덱스 모두 이동 시킨다.
                answer++;
                min++;
            }
            else { // limit 초과의 경우 뒤의 인덱스만 이동시킨다.
                answer++;
            }
        }
        return answer;
    }
    
}