[アルゴリズム]プログラマー:救命ボート
4249 ワード
プログラマー貪欲法：救命ボート
もんだいぶんせき
しゅろんり
一番軽い人と一番重い人を縛って乗船させると使用する船の数が減ります.
最も軽い→最も重い人の順に昇順に並べます
最初のインデックス(最も軽い人)と最後のインデックス(最も重い人)をlimitと比較
トラブルシューティング
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
// 가장 가벼운->무거운 순으로 정렬
Arrays.sort(people);
int len = people.length;
int cnt = 0;
// 최대한 가장 가벼운 사람 + 가장 무거운 사람의 조합으로 넣기 위해 양쪽 끝에서부터 이동
// 둘의 합이 limit을 초과하면 가장 무거운 사람은 나머지 다른 사람들과 같이 타도 무조건 limit 초과
int leftIdx = 0, rightIdx = len - 1;
int boat = 0;
while (cnt < len) {
if (people[leftIdx] + people[rightIdx] <= limit) {
leftIdx++; rightIdx--;
cnt += 2;
} else {
rightIdx--;
cnt++;
}
boat++;
}
return boat;
}
}注意事項
さらに
Reference
この問題について([アルゴリズム]プログラマー:救命ボート), 我々は、より多くの情報をここで見つけました https://velog.io/@nohyoonko/알고리즘-프로그래머스-구명보트テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol