Aggressive Cows

Q: Aggressive Cows의 시간 복잡도는 얼마인가요?

정렬에는 O(n log n) 이 걸리고 이진 탐색에는 O(n log D) 가 걸립니다. 여기서 D 는 마구간 범위를 k-1 로 나눈 값입니다. 정렬된 복사본을 제외하면 메모리는 O(1) 입니다.

Q: 왜 첫 번째 소는 항상 가장 왼쪽 칸에 들어가나요?

가능한 배치 중 하나를 선택해 가장 왼쪽에 있는 소를 가장 왼쪽의 축사로 옮기세요. 이 소는 다른 소들로부터 멀어지기만 하므로 거리가 줄어들지 않으며, 가장 왼쪽 축사를 사용하는 최적의 배치가 존재합니다.

Q: 정답에 대한 이진 탐색을 어떻게 알아볼 수 있을까요?

이 질문은 어떤 것이 가능한 가장 큰 값 또는 가장 작은 값을 묻습니다. 하나의 값이 가능한지 확인하는 것이 최적의 값을 찾는 것보다 훨씬 쉽고, 값이 커짐에 따라 답은 한 번만 바뀝니다. 여기서 값은 간격이고, 확인 방법은 그리디 배치입니다.

보통이진 탐색 정렬 그리디

+10

축사에는 일직선을 따라 축사 칸들이 있고, stalls[i]는 i번째 축사 칸의 위치입니다. 위치는 모두 서로 다르며 특별한 순서 없이 주어집니다. k마리의 소를 서로 다른 k개의 축사 칸에 넣어야 합니다. 소들은 가까이 서 있으면 싸우므로, 가장 가까운 두 소 사이의 거리를 가능한 한 크게 만들고 싶습니다.

소 두 마리 사이의 거리 중 가장 작은 값으로 가능한 최댓값을 반환하세요.

함수

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: 서로 다른 정차 위치를, 순서에 관계없이
kinteger: 배치할 소의 수
반환값integer: 두 소 사이의 가능한 최소 거리 중 가장 큰 값

제약 조건

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
stalls의 모든 위치는 서로 다릅니다.
2 ≤ k ≤ stalls.length

예제

입력: stalls = [10, 1, 7, 4, 15]k = 3
출력: 6
설명: 1, 7, 15에 있는 소들은 각각 6과 8만큼 떨어져 있습니다. 간격이 7이면 조건을 만족하지 않습니다. 1 다음에 소를 10에 놓게 되고, 17 이상인 곳에는 외양간이 없습니다.

후속 질문

가판대들이 원 위에 놓여 있어서 순서상 마지막 가판대가 첫 번째 가판대의 이웃이기도 하다면 무엇이 달라질까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

간격을 정하고 질문해 보세요. k마리의 소를 서로 최소한 그 간격만큼 떨어뜨려 세울 수 있을까요? 정렬된 축사를 한 번 탐욕적으로 훑으면 답을 구할 수 있습니다. 간격이 커지면 답은 한 번 ‘예’에서 ‘아니요’로 바뀌므로, 이분 탐색으로 마지막 ‘예’를 찾습니다.

정렬한 다음 각 간격을 차례로 시도하세요

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

핵심 아이디어

위치를 정렬합니다. 가장 가까운 두 소는 항상 이웃하므로, 이웃한 모든 소 쌍 사이의 거리가 최소 g라면 간격 g는 가능합니다.

간격이 가능한지 확인하려면 가장 왼쪽 외양간에 소 한 마리를 넣고, 마지막 소로부터 최소 g만큼 떨어진 외양간마다 소를 한 마리씩 넣습니다. 이 탐욕적인 배치는 어떤 배치보다 많은 소를 배치할 수 있습니다. 가능한 배치를 왼쪽부터 정렬해 보면, 탐욕적 배치의 소 i는 해당 배치의 소 i보다 오른쪽에 있지 않습니다. 따라서 탐욕적 배치는 다음 소를 위한 외양간을 더 늦지 않게 찾습니다.

간격 1은 항상 가능하므로 g = 2, 3, ...을 시도하고, k마리 미만의 소를 배치하는 첫 간격에서 멈춥니다. 첫 번째 예시에서는 간격 6으로 소 3마리를 배치할 수 있고 간격 7로는 2마리만 배치할 수 있으므로 답은 6입니다.

소가 두 마리이고 외양간이 0과 10^9에 있다면, 외양간 5000개를 약 10^9번 순회하게 되어 총 5 × 10^12단계가 걸립니다.

알고리즘

위치들을 정렬합니다.
간격 g에 대한 검사를 작성합니다. 소 한 마리는 pos[0]에 두고, 이후 pos[i] - last ≥ g인 모든 우리에 소 한 마리씩 배치하면서 소의 수를 셉니다.
gap = 1로 시작합니다.
gap + 1에 대한 검사로 소를 최소 k마리 배치할 수 있는 동안 gap에 1을 더합니다.
gap을 반환합니다.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

간격을 이용한 이진 탐색

핵심 아이디어

모든 간격이 g+1 이상인 배치는 모든 간격이 g 이상이기도 하므로, 검사 결과는 예, ..., 예, 아니요, ..., 아니요가 됩니다. 이진 탐색으로 마지막 예를 찾습니다.

항상 가능한 lo = 1에서 시작하고, hi는 구간의 길이를 k-1로 나눈 몫입니다. k마리의 소는 구간 안에 k-1개의 간격을 만들기 때문에, 가장 작은 간격은 이보다 클 수 없습니다. 조건을 만족하는 검사에서는 lo = mid로 설정하므로 mid는 올림해야 합니다. 내림하면 lo = 5와 hi = 6이 되어 무한히 반복됩니다.

첫 번째 예제에서 구간의 길이는 14이고 k = 3이므로 hi = 7입니다. 간격 4는 조건을 만족하고, 간격 6도 조건을 만족하지만, 간격 7은 조건을 만족하지 않으므로 범위는 6에서 좁혀집니다.

폭이 10^9까지인 범위는 5000개의 마구간을 약 30번 검사하면 좁혀지며, 대략 150,000단계가 걸립니다.

알고리즘

위치를 정렬합니다.
lo = 1로 설정하고 hi = (pos[n-1] - pos[0]) / (k-1)로 설정한 뒤, 내림합니다.
lo < hi인 동안 mid = lo + (hi - lo + 1) / 2를 계산합니다.
mid에서 탐욕적 검사를 수행했을 때 소를 최소 k마리 배치할 수 있으면 lo = mid로 설정하고, 그렇지 않으면 hi = mid - 1로 설정합니다.
lo를 반환합니다.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

함정과 경계 사례

정렬을 건너뛰는 경우. 정렬되지 않은 [10, 1, 7, 4, 15]에서 간격이 6이면, 검사는 10에서 시작하고 그보다 6만큼 뒤에 있는 축사를 찾지 못해 소 한 마리라고 보고합니다.
한 번의 검사에서 lo = mid를 설정하면서 mid를 내림하는 경우. hi = lo + 1이 되면 범위가 더 이상 줄어들지 않아 루프가 끝나지 않습니다.
소의 수가 정확히 k마리인지 확인하는 경우. 첫 번째 예시에서는 간격이 1일 때 소 5마리를 배치할 수 있습니다. 이는 3마리보다 많지만 간격은 유효합니다. count ≥ k인지 확인하세요.
소의 수를 0에서 시작하는 경우. 가장 왼쪽 축사의 소도 포함되므로 수는 1에서 시작합니다.

자주 묻는 질문3

Aggressive Cows의 시간 복잡도는 얼마인가요?

정렬에는 O(n log n)이 걸리고 이진 탐색에는 O(n log D)가 걸립니다. 여기서 D는 마구간 범위를 k-1로 나눈 값입니다. 정렬된 복사본을 제외하면 메모리는 O(1)입니다.

왜 첫 번째 소는 항상 가장 왼쪽 칸에 들어가나요?

가능한 배치 중 하나를 선택해 가장 왼쪽에 있는 소를 가장 왼쪽의 축사로 옮기세요. 이 소는 다른 소들로부터 멀어지기만 하므로 거리가 줄어들지 않으며, 가장 왼쪽 축사를 사용하는 최적의 배치가 존재합니다.

정답에 대한 이진 탐색을 어떻게 알아볼 수 있을까요?

이 질문은 어떤 것이 가능한 가장 큰 값 또는 가장 작은 값을 묻습니다. 하나의 값이 가능한지 확인하는 것이 최적의 값을 찾는 것보다 훨씬 쉽고, 값이 커짐에 따라 답은 한 번만 바뀝니다. 여기서 값은 간격이고, 확인 방법은 그리디 배치입니다.

def aggressiveCows(stalls, k):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

stalls = [10, 1, 7, 4, 15]
k = 3

예상 출력