탐욕법(Greedy)구명보트

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

프로그래머스

 

 

 

 

바로 이렇게 해서 풀릴줄 알았는데

 

이상하게 weight 가 limit 를 초과해도 조건문을 탄다

<= 이어서 100일 때도 더 추가로 태우기 때문

 

다시 짜고 실행했을 때 다 통과돼서 제출해봤더니 14점

 

 

애초에 접근이 잘못 됨

sort 해서 가벼운사람부터 태우면

20 30 40 50 60 70 과 같이 데이터가 있다면

20 30 40 태우고  

비운다음에 50 태우고

60 태우고

70 태워서

4번이 필요하지만

 

실제로는 페어에 잘맞게 태우는게 좋을 듯

30 70 태워서 100 꽉채우고

40 60 태워서 100 꽉채우고

50 20 태우면 3번만에 가능하다

 

결국 가장 효율적이려면 가벼운 순이 아닌 정렬 후 보트 무게에 딱 맞게 효율적으로 태워야 함

그리고 shift 보다는 pop 을 쓰는게 좀 더 효율적일 것 같다

끝에서 단순히 pop 하는건 O(1) 이지만 shift 는 O(N)일 것이다

자바스크립트에서는 가장 먼저 걸 빼온다음에 다시 재정렬하는 과정을 거칠 것 같으므로

차라리 pop 으로 구현하기로 

 

는 다 필요없고 

가장 큰 무게와 작은 무게 짝지어서 태워야 가장 효율적이라는 것을 몰랐음

function solution(people, limit) {
    people.sort((a, b) => a - b);
    let left = 0;
    let right = people.length - 1;
    let boats = 0;

    while (left <= right) {
        if (people[left] + people[right] <= limit) {
            left++;
        }
        right--;
        boats++;
    }

    return boats;
}