구명보트

구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885

 

문제에 대한 접근

1. 리미트를 초과하지 않는 최대의 무게를 구한다.
2. 일단 정렬해서 가장 작은 무게와 더 했을 때 리미트를 넘지 않는 가장 무거운 무게를 같이 탈출시킨다.
3.  

function solution(people, limit) {
    people.sort((a, b) => a - b)
    let idx = people.length - 1, answer = 0;
    while (people.length > 1) {
        if (people[0] + people[idx] < limit) {
            people.splice(idx, 1)
            people.shift()
            answer++
            idx = people.length - 1

        } else { idx-- }
    }

    return people.length === 0 ? answer : answer + 1;
}

결과는 맞지만 시간이 초과되었다. 

 

function solution(people, limit) {
    people.sort((a, b) => a - b)
    let idx = 1, answer = 0;
    while (people.length > 1 && people[0] + people[1] <= limit) {
    // 반복 횟수를 줄이기 위한 조건 추가
        if (people[0] + people[idx] > limit) {
            if (idx === 1) {
                people.shift()
                answer++
            } else {
                people.splice(idx - 1, 1)
                people.shift()
                answer++
                idx = 1
            }
        } else { idx++ }
    }

    return people.length === 0 ? answer : answer + people.length;
    // 리턴값 수정
}

시간이 조금 줄였다. 하지만 아직 시간이 초과된다.

 

충분히 고민했다고 판단되어 정답을 확인했다.

function solution(people, limit) {
    var answer = 0;
    people.sort((a, b) => b - a)
    for (var i = 0, j = people.length - 1; i <= j; i++) {
        console.log(people[j])
        if (people[i] + people[j] <= limit) j--
        answer++
    }
    return answer;
}

이제 분석하자 

 

가장 작은 값과 더 했을 때 두 명이 탈 수 있는 경우면 같이 빠지고, 한 명만 탈 수 있으면 가장 큰 값만 빠진다.

그래서 가장 작은 값부터 가장 큰 값을 더해가며 앞 뒤의 범위를 좁혀간다. 

마지막에 하나만 남은 경우 answer++ 종료, i=j

남은 두 숫자의 합이 리미트보다 작은 경우엔 i=j가 없음

 

핵심은 배열을 재정렬 하지 않는다. 이게 제일 중요하다. 배열을 재정렬하는 것 자체가 시간이나 자원 소모가 심하기 때문에 가능하면 주어진 배열을 건들지 않고 처리하는 게 좋다.

 

나중에 알게 된 내가 시간이 초과된 원인은 shift가 시간을 많이 잡아먹는다. (빠진 부분의 배열을 당겨야 하니까)