[코딩테스트] 구명 보트

나의 코드

function solution(people, limit) {
    var answer = 0;
    
    for (i = 0; i < people.length; i++) {
        var num = Math.max(...people); // 최댓값
        var index = people.indexOf(num); // 최댓값 위치
        
        var arr = people.map(a => a + num <= limit); 
        // 최댓값과 한 요소를 더 했을 때 limit보다 작은 건 true로 표시
        
        arr[index] = false; // 비교가 되는 최댓값은 무조건 false로 표시
        
        
        if (arr[i] === true) {
            arr = arr.splice(true, 1); // 판별 arr에서 true인 요소 제거
            arr = arr.splice(index, 1); // 판별 arr에서 최댓값 삭제
            
            people = people.splice(index, 1);
            people = people.splice(i, 1);
            
            return answer++;
        }
        
    answer++;
    }
    return answer;
}

/*
하나에 최대 2명씩, 무게 제한 존재
구명보트를 최대한 적게 사용해서 모든 사람을 구출

몸무게 담은 배열 people
무게 제한 limit

모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값 return

그러면... 제일 큰값 max 값을 구하고 그 값과 더했을 때 limit이 넘지 않는 애가 있는지 확인

*/

실패....

 

케이스 테스트는 성공했지만, 효율성 검사에서 실패...

function solution(people, limit) {
    var answer = 0;

    while (people.length > 0) {
        var num = Math.max(...people); // 가장 무거운 사람
        var index = people.indexOf(num);

        // 해당 사람을 먼저 제거하고
        people.splice(index, 1);

        // 짝이 될 수 있는 사람을 찾아본다
        var pairIndex = people.findIndex(a => a + num <= limit);

        if (pairIndex !== -1) {
            // 짝이 있으면 그 사람도 제거
            people.splice(pairIndex, 1);
        }

        answer++;
    }

    return answer;
}

 

 

성공 코드

function solution(people, limit) {
    people.sort((a, b) => a - b); // 정렬 (O(n log n))
    let left = 0;
    let right = people.length - 1;
    let answer = 0;

    while (left <= right) {
        if (people[left] + people[right] <= limit) {
            left++; // 가벼운 사람 태움
        }
        // 무거운 사람은 무조건 태움
        right--;
        answer++;
    }

    return answer;
}

 

다른 사람 코드

1.

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;
}

 

2.

function solution(people, limit) {
  let biggest = 0,
    count = 0,
    i = 0;
  people.sort((a, b) => a - b);
  while (people.length > 0) {
    biggest = people.pop();
    i = 0;
    while (people[i] <= limit - biggest) i++;
    if (i) people.splice(i - 1, 1);
    count++;
  }
  return count;
}