Assign Cookies

Q: Assign Cookies의 시간 복잡도는 무엇인가요?

두 배열을 정렬하는 데 O(n log n + m log m) 의 비용이 들고, 그 후 두 포인터로 순회하는 데는 O(n + m) 의 비용이 들므로 정렬이 전체 비용을 좌우합니다. 제자리에서 정렬하면 정렬 자체에 필요한 공간을 제외하고 추가 공간은 O(1) 로 유지됩니다.

Q: Assign Cookies에서는 왜 탐욕적 선택이 효과가 있을까요?

k 를 욕심이 가장 적은 아이에게 맞는 가장 작은 쿠키라고 하자. 최적의 배정에서 그 아이가 다른 쿠키를 받았다고 가정해 보자. 서로 바꾸면 그 아이는 k 를 받고, k 를 받았던 사람은 다른 쿠키를 받는다. 그 쿠키는 k 보다 크거나 같으므로 그 사람도 계속 만족한다. 만족하는 아이의 수는 바뀌지 않으므로, 최적의 배정은 항상 욕심이 가장 적은 아이에게 맞는 가장 작은 쿠키부터 배정할 수 있고, 남은 아이들과 쿠키에도 같은 논리를 반복해서 적용할 수 있다.

쉬움그리디 정렬

+10

각 아이 i에게는 욕심 지수 g[i]가 있습니다. 이는 아이를 만족시키는 가장 작은 쿠키 크기입니다. 각 쿠키 j에는 크기 s[j]가 있습니다. 아이는 욕심 지수 이상인 크기의 쿠키를 하나 받으면 만족합니다. 각 아이는 쿠키를 최대 하나만 받고, 각 쿠키는 아이를 최대 한 명만 만족시킬 수 있습니다. 만족시킬 수 있는 아이의 최대 수를 반환하세요.

함수

findContentChildren(g: integer-array, s: integer-array) → integer

ginteger-array: 각 아이의 욕심 계수, 즉 아이가 받아들일 수 있는 가장 작은 쿠키 크기
sinteger-array: 각 쿠키의 크기
반환값integer: 각자 욕심 계수만큼의 크기 이상의 쿠키를 받을 수 있는 최대 어린이 수

제약 조건

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
두 배열의 길이는 서로 다를 수 있으며, 어느 쪽도 정렬되어 있지 않습니다.

예제

입력: g = [4, 2, 7]s = [3, 5, 1, 2]
출력: 2
설명: 정렬하면, 아이들은 2, 4, 7을 원하고 쿠키는 1, 2, 3, 5입니다. 쿠키 2는 2를 원하는 아이에게 주고, 쿠키 5는 4를 원하는 아이에게 줍니다. 7에 도달하는 쿠키는 남아 있지 않으므로 답은 2입니다.

제출 시 숨은 테스트 +16개

후속 질문

각 아이에게 받아들일 수 있는 가장 큰 쿠키도 있다면 어떨까요? 그러면 쿠키는 일정 범위 안에서만 맞을 수 있습니다. 그렇다면 각 쿠키를 기다리는 아이 중 누구에게 주어야 할까요?

풀이

어떤 아이에게 어떤 쿠키를 줘야 하는지가 문제입니다. 모든 조합을 시도하면 경우의 수가 폭발적으로 늘어나지만, 하나의 그리디 규칙으로 해결할 수 있습니다. 가장 욕심이 적은 아이부터 만족시키고, 그 아이에게 맞는 가장 작은 쿠키를 주세요. 두 배열을 정렬한 뒤에는 두 개의 포인터로 한 번만 순회하면 됩니다.

각 아이에게 맞는 가장 작은 쿠키

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

아이들을 욕심이 가장 적은 순서부터 가장 많은 순서로 살펴봅니다. 각 아이마다 아직 사용하지 않은 쿠키를 모두 살펴보고, 그 아이에게 줄 수 있는 쿠키 중 가장 작은 것을 고릅니다. 맞는 쿠키가 없으면 그 아이는 계속 배고픈 상태로 남습니다. 첫 번째 예시에서 아이들이 원하는 양은 2, 4, 7입니다. 2를 원하는 아이는 쿠키 2를 받고, 4를 원하는 아이는 쿠키 5를 받으며, 7을 원하는 아이에게는 남는 쿠키가 없습니다.

왜 맞는 쿠키 중 가장 작은 것을 고를까요? 더 큰 쿠키는 작은 쿠키가 먹일 수 있는 모든 아이를 먹일 수 있고, 그보다 더 많은 아이도 먹일 수 있습니다. 조건을 만족하는 가장 작은 쿠키를 나눠 주면 나중에 차례가 오는 욕심 많은 아이들을 위해 더 큰 쿠키를 남겨 둘 수 있으므로, 먹일 수 있었던 아이를 놓치는 일이 없습니다.

문제는 탐색 비용입니다. n명의 아이가 각각 m개의 쿠키를 모두 살펴보므로, n = m = 5000이면 확인 횟수가 2,500만 번에 달해 가장 큰 테스트에서는 너무 느립니다.

알고리즘

욕심 계수를 작은 것부터 큰 것까지 정렬합니다.
각 쿠키가 사용되었는지 나타내는 플래그를 유지합니다.
각 어린이에 대해 모든 쿠키를 살펴보고, 크기가 해당 어린이의 욕심 계수 이상인 사용되지 않은 쿠키 중 가장 작은 것을 기억합니다.
쿠키를 찾았다면 사용된 것으로 표시하고, 해당 어린이를 만족한 것으로 셉니다.
개수를 반환합니다.

def findContentChildren(g, s):
    used = [False] * len(s)
    fed = 0
    for need in sorted(g):  # least greedy child first
        best = -1
        for j in range(len(s)):
            if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
                best = j
        if best != -1:
            used[best] = True
            fed += 1
    return fed

둘 다 정렬하고 투 포인터를 사용하세요

핵심 아이디어

위의 스캔은 맞는 쿠키 중 가장 작은 것을 계속해서 찾습니다. 쿠키도 정렬하면 이 탐색이 사라집니다. 쿠키가 크기 순으로 나열되므로, 맞는 쿠키 중 가장 작은 것을 먼저 만나게 됩니다.

쿠키를 가장 작은 것부터 가장 큰 것까지 확인하면서, 아직 기다리고 있는 아이 중 욕심이 가장 적은 아이를 가리키도록 포인터 child 하나를 유지합니다. 쿠키가 g[child]보다 크거나 같으면 그 아이에게 쿠키를 주고 포인터를 다음 아이로 옮깁니다. 쿠키가 더 작으면 정렬되어 있으므로 기다리는 모든 아이에게도 더 작습니다. 따라서 그 쿠키는 쓸모가 없고 다음 쿠키로 넘어갑니다.

첫 번째 예시에서 정렬된 쿠키는 1, 2, 3, 5이고, 정렬된 욕심 값은 2, 4, 7입니다. 쿠키 1은 2를 원하는 아이에게 너무 작습니다. 쿠키 2는 2를 원하는 아이에게 줍니다. 쿠키 3은 4를 원하는 아이에게 너무 작습니다. 쿠키 5는 4를 원하는 아이에게 줍니다. 포인터는 정답인 2에서 멈춥니다.

각 포인터는 앞으로만 이동하므로 순회는 O(n + m)이며, 두 번의 정렬이 전체 실행 시간을 좌우합니다. 제자리에서 정렬하면 추가 배열이 필요하지 않습니다.

알고리즘

g와 s를 오름차순으로 정렬합니다.
아직 기다리고 있는 욕심이 가장 적은 아이를 나타내도록 child = 0으로 설정합니다.
각 쿠키를 가장 작은 것부터 확인합니다. child가 여전히 g의 범위 안에 있고 쿠키가 g[child] 이상이면 child에 1을 더합니다.
음식을 받은 아이의 수인 child를 반환합니다.

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = 0  # the least greedy child still waiting
    for size in s:  # smallest cookie first
        if child < len(g) and size >= g[child]:
            child += 1
    return child

함정과 경계 사례

대부분의 오답은 잘못된 순서로 매칭하거나 잘못된 포인터를 이동해서 발생합니다.

아이에게 필요한 것보다 더 큰 쿠키를 줍니다. g = [1, 2]이고 s = [1, 3]일 때, 1을 원하는 아이에게 쿠키 3을 주면 2를 원하는 아이는 여전히 배고프지만, 올바르게 짝지으면 두 아이 모두에게 쿠키를 줄 수 있습니다.
쿠키가 너무 작을 때 아이 포인터를 이동합니다. 아이는 여전히 쿠키가 필요합니다. 쓸모없는 것은 쿠키입니다.
아이 포인터의 범위 검사를 잊습니다. 모든 아이가 쿠키를 받으면, 남은 쿠키를 확인할 때 g의 끝을 넘어 읽지 않도록 해야 합니다.
≥ 대신 >로 비교합니다. 욕심 계수와 크기가 정확히 같은 쿠키도 충분합니다.
숫자를 텍스트로 정렬합니다. JavaScript에서 비교자 없이 sort()를 호출하면 10이 9보다 앞에 옵니다.

자주 묻는 질문4

Assign Cookies의 시간 복잡도는 무엇인가요?

두 배열을 정렬하는 데 O(n log n + m log m)의 비용이 들고, 그 후 두 포인터로 순회하는 데는 O(n + m)의 비용이 들므로 정렬이 전체 비용을 좌우합니다. 제자리에서 정렬하면 정렬 자체에 필요한 공간을 제외하고 추가 공간은 O(1)로 유지됩니다.

Assign Cookies에서는 왜 탐욕적 선택이 효과가 있을까요?

k를 욕심이 가장 적은 아이에게 맞는 가장 작은 쿠키라고 하자. 최적의 배정에서 그 아이가 다른 쿠키를 받았다고 가정해 보자. 서로 바꾸면 그 아이는 k를 받고, k를 받았던 사람은 다른 쿠키를 받는다. 그 쿠키는 k보다 크거나 같으므로 그 사람도 계속 만족한다. 만족하는 아이의 수는 바뀌지 않으므로, 최적의 배정은 항상 욕심이 가장 적은 아이에게 맞는 가장 작은 쿠키부터 배정할 수 있고, 남은 아이들과 쿠키에도 같은 논리를 반복해서 적용할 수 있다.

가장 욕심 많은 아이부터 시작할 수 있나요?

네. 두 배열을 모두 정렬한 다음, 가장 큰 쿠키와 가장 욕심 많은 아이부터 살펴보세요. 남은 쿠키 중 가장 큰 쿠키가 남은 아이 중 가장 욕심 많은 아이에게 맞으면, 그 아이에게 쿠키를 주고 두 포인터를 모두 이동하세요. 그렇지 않으면 어떤 쿠키로도 그 아이를 만족시킬 수 없으므로 아이를 건너뛰세요. 같은 시간에 같은 개수를 얻습니다.

Assign Cookies는 동적 프로그래밍 문제인가요?

아닙니다. 교환 논증은 그리디 선택이 항상 안전하다는 것을 보여 주므로, 정렬한 뒤 한 번 순회하는 것으로 충분하며 시간 복잡도는 O(n log n + m log m)입니다. 두 정렬된 배열을 대상으로 최장 공통 부분 수열 표처럼 채우는 표를 사용해도 답을 구할 수 있지만, 같은 결과를 얻는 데 O(n × m)의 시간이 듭니다.

Python

def findContentChildren(g, s):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

g = [4, 2, 7]
s = [3, 5, 1, 2]

기대값