프로그래머스 42885 - 구명보트

첫번째 접근 방법

people 리스트를 sort후 앞 인덱스부터 구명보트를 채워나갈것

=> 이렇게 하면 입출력 예제는 다 통과가 되지만 다음경우는 되지 않는다

[ 100, 500, 500, 900, 950 ] => 위의 알고리즘으로는 4가 나오지만 정답은 3이다. (100, 900), (500, 500), (950)

 

두번째 접근 방법

일단 가장 많이 태울 수 있는 법은 무게가 가벼운 사람 + 무게가 무거운 사람을 세트로 하여야한다.

people 리스트를 정렬 후 맨 앞과 맨 뒤를 비교한다. (가장 큰 값과 가장 작은 값)

두 개의 합이 100 이하이면 인덱스를 한 칸씩 중앙으로 당겨온다

100이 초과되면 그 다음으로 큰 값과 비교를 한다.

 

def solution(people, limit):
    answer = 0
    people.sort()

    start, end = 0, len(people) - 1
    
    while start <= end:
        answer += 1
        if people[start] + people[end] <= limit:
            start += 1
        end -= 1
    
    return answer