13일 - 사람을 구하는 배

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

예 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

예 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

예 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

메모:

1 <= people.length <= 50000

1 <= people[i] <= limit <= 30000

내 테스트

Link to code

import pytest
from .Day13_BoatsToSavePeople import Solution

s = Solution()


@pytest.mark.parametrize(
    "people,limit,expected",
    [
        ([1, 2], 3, 1),
        ([3, 2, 2, 1], 3, 3),
        ([3, 5, 3, 4], 5, 4),
        ([2, 2], 6, 1),
        ([3, 1, 7], 7, 2),
        ([2, 4], 5, 2),
    ],
)
def test_num_rescue_boats(people, limit, expected):
    assert s.numRescueBoats(people, limit) == expected

내 솔루션

Link to code

from typing import List


class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        boats = 0
        i = 0
        j = len(people) - 1
        while i <= j:
            i = i + 1 if people[i] + people[j] <= limit else i
            boats += 1
            j -= 1
        return boats

분석

내 해설

나는 이것을 위해 목록을 정렬할 필요가 없도록 모든 방법을 시도했습니다. 나는 계산을 저장하기 위해 HashMap을 사용하는 것과 같은 미친 짓을 시도했지만 먼저 목록을 정렬할 필요가 없는 더 나은 성능의 솔루션이 있다면 현재 그것을 알아낼 수 없습니다.

위의 솔루션에서 먼저 사람을 가장 가벼운 것부터 가장 무거운 것까지 무게순으로 정렬합니다. 다음과 같은 요구 사항이 있었습니다.

Each boat carries at most 2 people at the same time

가장 무거운 사람과 가장 가벼운 사람이 들어갈 수 있는지 확인만 하면 되기 때문에 이런 종류의 작업은 작업을 더 쉽게 만듭니다. heaviest + lightest > limit이면 heaviest와 다른 어떤 조합도 작동하지 않습니다.

그 사실을 감안할 때 우리는 각 반복에서 가장 무겁고 가벼운 것을 봅니다. 둘 다 맞으면 한 척의 보트로 계산합니다. 그렇지 않은 경우 가장 무거운 사람은 자신의 보트를 얻습니다. 각 사람이 보트로 운반될 수 있기 때문입니다. 이 경우 가장 가벼운 사람에게 색인을 유지하고 다음으로 무거운 사람과 함께 확인합니다.
people.sort()는 여기에 log N이고 우리는 O(N log N)를 제공하는 보트를 세기 위해 목록을 한 번 더 살펴봅니다.