문제 설명
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
위 문제는 한명 아니면 두 명만 보트를 탈 수 있다.
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
Arrays.sort(people);
int count = 0;
for (int start = 0, end = people.length - 1;;) {
if (start > end){
break;
} else if (start == end){
count++;
break;
}
if (people[start] + people[end] <= limit){
count++;
start++;
end--;
} else if (people[start] + people[end] > limit){
count++;
end--;
}
}
return count;
}
}내가 푼 방법은 먼저 배열을 정렬 후 몸무게가 가장 적은 사람과 몸무게가 가장 많은 사람을 매칭시켜 제한 무게와 같거나 제한 무게보다 적은 경우 start와 end 모두 이동시키고 count를 증가시킨다.
매칭시킨 무게가 제한 무게보다 큰 경우 몸무게가 큰 사람만 보트에 태워서 보내야 하기 때문에 end만 이동시키고 count를 증가시킨다.
몸무게가 가장 큰 사람과 가장 작은 사람을 매칭해서 제한을 넘으면 가장 큰 사람은 배열에 존재하는 누구와 매칭해도 제한 초과이기 때문에 큰 사람만 보내야 한다.
종료 조건으로 start가 end를 넘으면 남은 사람이 없는 것이기 때문에 종료시킨다.
다른 조건으로는 start와 end가 같으면 1명이 남은 것이기 때문에 count를 하나 증가하고 종료한다.
위 문제는 그리디 알고리즘을 이용해서 푸는 문제이다.
그리디 알고리즘(탐욕법, Greedy Algorithm) 이란?
- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 '각 단계에서 최적이라고 생각되는 것을 선택'해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.
- 이때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 복표로 하고 있다.
- 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.
그리디 알고리즘의 단계
1. 문제의 최적해 구조를 결정한다.
2. 문제의 구조에 맞게 선택 절차를 정의한다: 선택 절차(Selection Procedure)
3. 선택 절차에 따라 선택을 수행한다.
4. 선택된 해가 문제의 조건을 만족하는지 검사한다: 적절성 검사(Feasibility Check)
5. 조건을 만족하지 않으면 해당 해를 제외한다.
6. 모든 선택이 완료되면 해답을 검사한다: 해답 검사(Solution Check)
7. 조건을 만족하지 않으면 해답으로 인정되지 않는다.
