[그리디] 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885#

 

첫번째 (성공)

• 무게를 오름차순으로 정렬
• 최소, 최대 무게의 합이 limit 이하면 answer을 더하고 최소, 최대를 빼준다
• limit이상이면 최대만 뺀다.

function solution(people, limit) {
    var answer = 0;
    people.sort((a, b) => a -b);
    while(people.length) {
        if (people[0] + people[people.length-1] <= limit) {
            people.pop();
            people.shift();
        } else {
            people.pop();
        }
        answer++;
    }
    return answer;
}

 

두번째 방법(성공)

근데 새로 추가된 테케 때문인지 가끔 효율성4번이 시간초과가 남 (왜 그런지 아시는 분 알려주시면 감사하겠습니다!)

function solution(people, limit) {
    var answer = 0;
    people.sort((a, b) => a - b);
    let left = 0;
    let right = people.length-1;
    
    while(left < right) {
        // 2명이 구명보트를 탈 수 있을 때
        if (people[left] + people[right] <= limit) {
            answer++;
            left++;
            right--;
        } else {
            right--;
        }
    }
    answer += people.length-answer*2;
    return answer;
}