코딜리티 L14_MinMaxDivision 파이썬 (이진탐색)

2023-03-18

코딜리티 L14_MinMaxDivision 파이썬

참고: MinMaxDivision coding task - Learn to Code - Codility

무엇?

1. 배열 A를 K개 이하의 블럭으로 나눔
   • 반드시 1개 이상의 블럭
   • 블럭의 길이는 0일 수도 있음
2. 배열 A의 원소의 크기는 M 이하 (※ 최댓값이 M이라는 뜻이 아님)
3. 블락 총합의 최댓값이 가장 작은 것을 구하기

어떻게?

이진탐색 반복문 사용

• 배열 나누기 확인 함수 (주어진 sum 값을 최대 sum 값으로 유지하면서 배열을 K개로 쪼갤 수 있는지 확인)

1. A의 원소에 대해서
   1. 블럭의 합과 원소를 더한 값이 맞춰야 할 최대 합보다 크다면:
      1. 블럭을 쪼갠다 (합을 해당 원소 값으로 리셋)
      2. 블럭 개수가 K개를 넘기면: 배열을 나눌 수 없다는 뜻!
   2. 블럭의 합과 원소를 더한 값이 맞춰야 할 최대 합보다 작다면: 블럭 합에 해당 원소를 더하여 업데이트

• 이분탐색 함수

3. 0부터 최대 합까지 범위 지정
4. mid 값을 minimal large sum으로 리스트를 쪼갤 수 있는가:
   1. 가능하면 -> answer에 할당 + 배열의 왼쪽 탐색
   2. 불가능하면 배열의 오른쪽 탐색

def is_splited(large_sum, A, K):
    block_sum = 0
    block_count = 0

    for a in A:
        if (block_sum + a > large_sum): # a를 더한 값과 비교해야 건너뛰는 값이 없음
            block_sum = a               # sum을 구할 원소 기준 재설정
            block_count += 1
            if block_count == K:        # K개로 쪼개려면 block_count는 K 미만이여야 함
                return 0
        else:
            block_sum += a

    return 1


def solution(K, M, A):
    N = len(A)
    answer = M * N
    high = sum(A)
    low = max(A) # low를 0으로 잡아야 엣지 케이스 통과

    if K == 1:
        return high
    if K >= N:
        return low
    if high == low:
        return low

    while low <= high:
        mid = (low + high) // 2
        if (is_splited(mid, A, K) == 1):
            answer = min(mid, answer)
            high = mid - 1
        else:
            low = mid + 1

    return answer

이진탐색 재귀함수 사용

def is_splited(large_sum, A, K):
    block_sum = 0
    block_count = 0

    for a in A:
        if (block_sum + a > large_sum):  # a를 더한 값과 비교해야 건너뛰는 값이 없음
            block_sum = a               # sum을 구할 원소 기준 재설정
            block_count += 1
            if block_count == K:        # K개로 쪼개려면 block_count는 K 미만이여야 함
                return 0
        else:
            block_sum += a

    return 1


def search(low, high, A, K, answer):
    if low > high:
        return answer
    else:
        mid = (low + high) // 2
        if (is_splited(mid, A, K) == 1):
            answer = min(mid, answer)
            return search(low, mid-1, A, K, answer)
        else:
            return search(mid+1, high, A, K, answer)


def solution(K, M, A):
    N = len(A)
    answer = M * N
    high = sum(A)
    low = max(A) # low를 0으로 잡아야 엣지 케이스 통과

    if K == 1:
        return high
    if K >= N:
        return low
    if high == low:
        return low
    
    answer = search(low, high, A, K, answer)
    return answer

try-error

1. 배열 나누기 함수에서 블럭 합에 해당 원소를 더한 값과 비교해야 정확함
2. 블럭의 개수를 판별할 때 K개로 쪼개기 위해서, count는 K-1까지 유효하며, K부터 블럭 개수 초과
3. 다음과 같은 케이스에 유의할 것
   1. block의 length가 0일 수도 있음
   2. 모두 0인 배열 A
   3. K가 배열의 길이와 같거나 크다면?
   4. K가 1이라면?
   5. 다 더한 값이 A의 최댓값과 같다면?
   6. M보다 크지 않다는 말이, 최대값이 곧 M이라는 뜻은 아님!!! (※ low 바운드를 잡을 때 참고한다)