파비의 매일매일 공부기록

2023.04.03 Today's Challenge 본문

Problem Solving/LeetCode

2023.04.03 Today's Challenge

fabichoi 2023. 4. 3. 23:45

https://leetcode.com/problems/boats-to-save-people/

 

Boats to Save People - LeetCode

Can you solve this real interview question? Boats to Save People - You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most

leetcode.com

탐욕법으로 풀면 될거 같은데, edge case 때문에 WA 날 듯.
그럴 땐 투 포인터 기법을 활용하면 됨.

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i, j = 0, len(people) - 1
        ans = 0

        while i <= j:
            ans += 1
            if people[i] + people[j] <= limit:
                i+= 1
            j -= 1
        
        return ans
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.04.05 Today's Challenge  (0) 2023.04.05
2023.04.04 Today's Challenge  (0) 2023.04.04
2023.04.02 Today's Challenge  (0) 2023.04.02
2023.04.01 Today's Challenge  (0) 2023.04.01
2023.03.31 Today's Challenge  (0) 2023.03.31
'Problem Solving/LeetCode' Related Articles more
Comments