프로그래머스 [구명보트] - 그리디 Lv.2

그리디

• 최종적으로 최선의 결과를 내기 위해 현재 상황에서 가장 최선의 방법을 선택하는 것을 반복하는 알고리즘이다.

그리디를 이용한 로직

• 문제에서 제시한 것처럼, 최소한의 구명보트 갯수로 모든 사람을 운송해야 한다.
• 단 조건은 보트에는 2명까지만 탈 수 있고, 보트의 허용 무게를 초과해서는 안된다.
• 이 상황에서 최소한의 보트로 최대한 많은 사람을 운송하기 위한 방법은
• 가장 무거운 사람을 우선적으로 운송하는 것이다.
• 그렇게 되면 가벼운 사람들만 남게 되며 두 명씩 채워서 운송하게 될 확률이 높아진다.
• 따라서 우선적으로 가장 무거운 사람을 운송하기 위한 방법은
• 가장 무거운 사람과 가장 가벼운 사람을 같이 태워보는 것이다.(가장 무거운 사람 두 명을 태우면, 보트에 두 명 타게 될 확률은 거의 없다.)
• 만약 둘을 같이 태울 수 있다면 같이 태우고, 그게 안된다면 가장 무거운 사람만 태운다.
• 위 과정을 반복한다.

내가 작성한 코드

function solution(people, limit) {

    people.sort((a, b) => a - b)
    
    let answer = 0
    
     while(people.length > 0) {
         if(people[people.length - 1] + people[0] > limit) {
   	         people.pop()
             answer += 1
         } else {
             people.pop()
             people.shift()
             answer += 1
         }
     }
    
    return answer
}

하지만 위와 같이 작성하고 제출하면, 효율성 테스트 케이스 1번이 불합격 처리 된다.
두 명을 같이 태우는 경우의 shift연산 때문이다. 사람들 목록을 O(N)만큼을 반복하게 되어 시간 초과가 발생하였다.
따라서 아래와 같이 인덱스로 접근하는 방식으로 수정하여 해결하였다.

function solution(people, limit) {

    people.sort((a, b) => a - b)

    let answer = 0
    
    let left = 0	// 왼쪽 인덱스 
    let right = people.length - 1	// 오른쪽 인덱스
    
    while((right - left) >= 0) {
        if(people[right] + people[left] > limit) {
            right -= 1
            answer += 1
        } else {
            right -= 1
            left += 1
            answer += 1
        }
    }
    
    return answer
}