PROGRAMMERS 구명보트

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

input :

• people limit

output :

• 필요한 구명보트 개수의 최솟값을 반환하시오.

조건 :

• 구명보트는 한 번에 최대 2명씩 밖에 탈 수 없다.
• 구명보트는 무게 제한이 있다.

---

idea

• 최대 탑승인원이 2명이기에 가장 무거운 사람들을 태우고 가벼운 사람이 같이 탈 수 있는지 확인한다.
• 우선적으로 정렬을 한다.
• 투포인터 방식으로 가장 큰 인덱스의 사람은 언제나 보트에 태운다.
• 작은 인덱스의 사람 또한 해당 보트에 태울 수 있는지 확인한다. 가능하다면 l += 1을 통해 해당 인원을 제외한다.

주의

• 타는 사람은 .. 2명이다.
• [40, 40, 45, 100, 100, 120, 155]와 같은 경우에는 어떻게 해야 하는가 생각하다가 위의 조건 잊어버렸다.

def solution(people, limit):
    people.sort()
    l, r = 0, len(people) - 1
    
    cnt = 0
    while l <= r:
        cnt += 1
        lval, rval = people[l], people[r]
        if lval + rval <= limit:
            l += 1
        r -= 1
        
    return cnt