탐욕법 - 구명보트

이 문제는 주어진 사람들을 구명보트의 무게 제한에 맞게 최대한 효율적으로 태워야 하는 문제이다. 두 명의 사람을 한 보트에 최대한 태우도록 하면서도 보트의 수를 최소화해야한다. 

 

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        
        
        int i = 0;
        for (int j=people.length - 1; i <= j; j--) {
            if(people[i] + people[j] <= limit) {
                i++;
            }
            answer++;
        }
        return answer;
    }
}

문제 풀이

1. 먼저 사람들의 몸무게를 정렬 해준다.

2. 양 끝에서 시작 하여 가장 가벼운 사람을 왼쪽 끝과 가장 무거운 사람을 오른쪽 으로 설정해야한다. i 가 왼쪽 j 가 오른쪽

3. 두 사람의 몸무게 합이 보트의 제한 무게를 넘지 않으면, 둘 다 보트에 태우고 i 와 j를 모두 이동시켜준다. 그렇지 않으면 가장 무거운 사람만 태우고 j 만 감소한다.

4. 보트가 사용될 떄 마다 answer 를 증가 시켜준다.

 

 

 

Script

-------------------------------------------------------------------

시간 복잡도를 따지면 사람의 수를 n 이라 할때, 정렬에 O(n log n) 그 후의 탐색에 O(n) 시간이 걸린다. 문제의 조건을 총족하며 효율적으로 사람들을 구명보트에 태워 최소한의 보트 수를 계산을 해야한다. 어떤 코드이든 정렬을 한번 해주고 어떤 방식으로 코드를 작성할지 잘 생각해서 코드를 작성하는것이 중요하다.