Lv.2 : 구명보트 [JavaScript]

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

프로그래머스

---

문제 풀이 1 =>  효율성 테스트 실패 (시간 초과)

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

people을 내림차순으로 정렬해서

sortedPeople[0] 제일 무거운 사람과 sortedPeople[sortedPeople.length -1] 제일 가벼운 사람의 무게 합이 limit보다 같거나 적으면 둘을 태울 수 있으므로 shift로 제일 무거운 사람을 제거, pop으로 제일 가벼운 사람을 제거한 후 answer++

limit보다 크면 제일 무거운 사람만 태울 수 있으므로 shift 후 answer++

 

이 방법대로 하면 정확성 테스트는 통과하지만 효율성 테스트에서 시간 초과가 난다

 

이유를 찾아보니, pop()은 시간 복잡도 O(1) 이지만, shift()는 O(n)을 가지기 때문에 shift를 두 번이나 사용해 초과가 난 것으로 보인다.

 

push()/pop() => O(1) : 배열의 맨 끝 요소를 추가/제거만 하기 때문

shift()/unshift() => O(n) : 배열의 첫 번째 요소를 추가/제거하고 나머지 요소를 오른쪽/왼쪽으로 이동시키기 때문

 

문제 풀이 2 =>  효율성 테스트 통과

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

people을 내림차순으로 정렬해서

pop을 두 번 사용하도록 수정하니, 효율성 테스트를 통과했다