[Coding Test | Programmers] -lifeboat (Java)

구명보트

Approach

그리디 문제를 계속 풀면서 푸는 방법을 어느 정도 익힌 거 같다.
그리디는 지금 최선의 값을 찾는 알고리즘이다. 주의할 점은 특정 조건에서만 돌아가는 로직이 아닌 모든 데이터에 부합하는 조건을 찾아야 한다. 이러한 조건을 맞추기 위해 우리는 정렬이나 범위를 정해주는 식으로 데이터를 가공해서 사용해야 한다.

이 문제의 경우 최선의 방법은 보트에 2명씩 많이 태우면 원하는 결과가 나올 것이다. 여기서 2명의 무게를 구하려면 배열을 한번 검색을 해야하기때문에 시간복잡도가 늘어난다. 그래서 정렬을 해주어서 이 부분을 해결해야 한다.
다음으로 해결해야 할 조건은 구명보트에 가능한 최대 무게로 태우는 것이다. 그래야 가장 적은 보트를 사용하게 된다.
이렇게 그리디 문제는 이러한 조건을 찾고 구현해 내는 것이 관건인 거 같다.

Algorithm & Data Structure

Sort

Time Complexity

O(n)

Code

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int[] selected = new int[people.length -1];
        
        Arrays.sort(people);
        
        int minimumPerson = 0;
        int maximumPerson = people.length -1;
        
        while(maximumPerson >= minimumPerson){
            int sum = people[minimumPerson] + people[maximumPerson];
            if (sum > limit){
                answer++;
                maximumPerson--;
            }else{
                answer++;
                minimumPerson++;
                maximumPerson--;
            }
        }
        
        return answer;
    }
}