dfs로는 시간초과 발생한다..
function solution(people, limit) {
let ch = Array.from({length:people.length}, () => 0);
let tmp = [];
let max = Number.MAX_SAFE_INTEGER;
function Rescue (L) {
if (L===people.length) {
let cnt=0;
let answer=[];
for (let i=0; i<tmp.length; i++) {
if (answer.length==0) {
answer.push(tmp[i]);
}
else if (answer.length==1) {
if (answer[0]+tmp[i] <= limit) {
answer.shift();
cnt++;
}
else if (answer[0]+tmp[i] > limit) {
answer.shift();
cnt+=2;
}
}
}
if (answer.length !== 0) cnt++;
max = Math.min(max, cnt);
// console.log(tmp, answer, cnt);
}
else {
for (let i=0; i<people.length; i++) {
if (ch[i]==0) {
ch[i]=1;
tmp[L]=people[i];
Rescue(L+1);
ch[i]=0;
tmp.pop();
}
}
}
}
Rescue(0)
return max;
}
console.log(solution([70, 50, 80, 50], 100));
그리디 알고리즘
시작점과 끝지점을 설정하고,
구명보트에 최대 2명씩 밖에 탈수 없기 때문에 가장 많이 탈 수 있는 방법은 가장 무거운 사람과 가장 가벼운 사람이 타는 방법 뿐임.
function solution(people, limit){
var answer = 0
people.sort((a,b) => b-a)
let l = 0
let r = people.length-1
while(l<r){
var sum = people[l] + people[r]
if(sum>limit){
l++ // 혼자 탄 배 answer++;
} else {
l++ // 함께 탄 배 answer++;
r--
}
answer++
}
if(l == r) answer++ // 계산되지 않은 애는 혼자타는 배로 answer++;
return answer
}
console.log(solution([70, 50, 80, 50], 100));
호이스팅(var i)을 활용한 풀이
function solution(people, limit) {
people.sort(function(a, b){return a-b});
for(var i=0, j=people.length-1; i < j; j--) {
if( people[i] + people[j] <= limit ) i++;
}
return people.length-i;
}
console.log(solution([70, 80, 50], 100));