[알고리즘] 프로그래머스 - 구명보트

프로그래머스 - 구명보트

내 풀이

def solution(people, limit):
    people.sort()
    cur_max = limit
    count = 0
    left, right = 0, len(people) - 1
    while left <= right:
        while left <= right and people[right] <= cur_max:
            cur_max -= people[right]
            right -= 1

        while left <= right and people[left] <= cur_max:
            cur_max -= people[left]
            left += 1

        count += 1
        cur_max = limit

    return count

처음에는 대충 생각하고 역순으로 정렬한 다음, 하나씩 꺼내서 비교하는데 무게가 초과하면 새 보트를 꺼내는 식으로 구현했다. 하지만 그렇게하면, 낭비되는 공간이 있고, 그 낭비되는 공간에 몸무게가 작은 사람들을 넣을 수 있다. 따라서 투포인터로 큰 사람을 넣을만큼 넣어보고, 안되면 그때 작은 사람을 넣어보고 안되면 새 보트를 쓰면 된다.