[프로그래머스] 구명보트 - 자바스크립트

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

코딩테스트 연습 - 구명보트

효율성 테스트가 가장 힘들었던거 같다.

문제 플로우는 다음과 같다

1. 사람을 무게순으로 정렬(내림차순)

2. 가장 가벼운사람과 가장 무거운사람의 무게 합이 리밋보다 작다면 있다면, answer++, 그리고 두사람을 리스트에서 제외한다. 만일, 리밋보다 크다면 answer++을 하고, 가장 무거운사람만 리스트에서 지운다.

answer을 리턴을 하면되지만... 여기서 경우의 수가 너무많이 있다고하면 while에서 시간 초과가 나오기 때문에,

3. 만일 가장 무거운사람의 무게가 리미트에 절반이라면 남아있는 리스트의 숫자 나누기2를 하고 answer에 더한다

(주의 : 여기서 말하는 가장 무거운 사람은, 계속 리스트를 shift()시키기 때문에 while을 시행할 때마다 바뀐다)

그랬는데... 시간 초과가 떴다. 그래서 고민을 해봤는데, 여기서 array를 slice하는 과정에서, 많은 시간이 소요된거 같다. array의 삭제와 같은경우에는, O(n)이 걸리기 때문인거 같았다. 

아래는 이를 array의 삭제를 이용한경우

function solution(people, limit) {
    let sort = people.sort((a,b)=>b-a)
    let answer = 0;
    while(sort.length!==0){
        if(sort[0]<=limit/2){
        answer = answer+Math.ceil(sort.length/2);
        return answer;
        }
        if(sort[sort.length-1]>limit/2){
            answer = answer+sort.length;
            return answer;
        }

        if(sort[0]+sort[sort.length-1]<=limit){
        sort.shift()
        sort.pop()
        answer++
        }else{
        sort.shift()
        answer++
        }
    }
    return answer
}

당연하게도 시간초과가 떴다.

다음과 같은 경우에는, 첫번째 사람과 두번째사람을 각각 더하고 빼면서, array의 탐색을 이용하여 풀이를 했다.

1. 사람을 무게순으로 정렬한다(위와 같음)

2. 맨앞번호를 first, 맨뒷번호를 second로 등록한다

3. first와 second의 합이 리미트보다 작다면 first++ second--를 시킨다.

4. sort[first]가 리미트보다 작거나 같다면 first-second+1을 2로 나누고 반올림을 한값을 더하고 answer를 return한다

function solution(people, limit) {
    let sort = people.sort((a,b)=>b-a)
    let answer = 0;
    let first = 0
    let second = sort.length-1
    while(first<=second){
    if(sort[first]<limit/2){
        return Math.ceil((second-first+1)/2)+answer
    }
    if(sort[first]+sort[second]<=limit){
    first++
    second--
        answer++
    }else{
        first++
        answer++
    }
    }
    return answer
}

 

문제 효율성 풀이에 있어서, 빅오를 신경 쓴 첫번째 케이스인거 같다.(내가 푼문제중에) 앞으로 효율성이 문제가 된다면 array를 잘못 사용하였구나라고 생각해야겠다.