[프로그래머스] level.2 구명보트 (**)

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

프로그래머스

 

나의 풀이 

 

function solution(people, limit) {
    people.sort((a,b) => b - a)
    let Maxboat = []
    let box = []
    people.map(x => x > limit/2 ? Maxboat.push([x]) :box.push(x))
    for(i=0, k=Maxboat.length - 1; i<box.length; i++){
        if(Maxboat[k] && +Maxboat[k][0] + +box[i] <= limit && Maxboat[k].length < 2 ){
            Maxboat[k].push(box[i])
            box.splice(i,1)
            k--
        }
    }
    return Maxboat.length + Math.ceil(box.length/2)
}

이건 정답이 안된다.  제출 하면 4개만 맞고 효율성도 2개만 맞는다. 

 

원리는 내림차순으로 정렬한 뒤 

 

limit/2 보다 크면 일단 보트에 각각 다 태웠고 아닌 사람은 따로 box로 모았다. 

그런뒤 for문에서 보트에 이미 타고 있는 인원들에서 제일 가벼운 사람 + box에서 제일 무거운 사람을 더 한뒤 limit를 넘지 않으면 보트에 태우고 그렇지 않으면 box에서 다음 가벼운 사람과 또 더하는 식이다. 

 

질문하기에 있는 모든 테이스트 케이스를 넣어서 통과를 했지만 정작 제출을 누르면 4개만 통과한다 

 

 

다른 사람 풀이 

 

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

제일 작은 값과 제일 큰 값을 더 해서 제한 무게를 초과하지 않으면 보트에 태우고 아니면 pass

j는 지속적으로 작아지고  보트에 탈 때만 i가 증가한다. 

 

그래서 최종적으로 people.length - i로 최솟값을 구한다. 

전체 사람중에 보트에 탄 쌍을 빼주는 것이다. 

 

이 풀이는 아예 배열조작이 필요하지 않아 엄청 빠르다.