[Codility] Lesson14. MinMaxDivision (Python)

1.문제

https://app.codility.com/c/run/training77EUN5-7HZ/

Codility

 

2.풀이

어느 회사에 코딩테스트로 비슷한 문제가 나왔었던 문제. 그 당시에는 완전탐색 문제인 줄 알았는데 이 문제를 풀면서 이분탐색을 적용해서 푸는 문제였다는 것을 알았다. 아무리생각해도 어떻게 풀어야할지 몰라서 구글링해서 참고하였다.. ㅎㅎ

case1. K == len(A) 일 경우 : 모든 원소의 sum 반환

case2. K >= len(A) 일 경우 : 만약 A=[1, 5], K=3 이면 [],[1],[5] 이므로 max(A) 를 반환

case3. 그 외의 경우: 이분탐색을 통해 K개 만큼 블록이 나누어지면 upper_boun = mid - 1 , 안 나누어지면 lower_bound = mid+1 로 한 블록의 최대값이 가장 작아지는 경우를 찾는다.

 

3.코드

#K개만큼 블럭이 생기는지 확인
def isValid(A, max_block_cnt, max_block_size):
    block_sum = 0
    block_cnt = 0

    for ele in A:
        #block의 최대값을 넘어가면 블록 나누기
        if block_sum + ele > max_block_size:
            block_sum  = ele
            block_cnt += 1
        #블록안의 원소 값 sum
        else:
            block_sum += ele
        if block_cnt >= max_block_cnt:
            return False
    return True


def solution(K, M, A):
    max_block_cnt = K
    lower_bound = max(A) #각 블록 sum의 최소값
    upper_bound = sum(A) #모든 블록의 sum 값

    if max_block_cnt == 1:
        return upper_bound
    if max_block_cnt>= len(A):
        return lower_bound

    while(lower_bound <= upper_bound):
        mid = (lower_bound + upper_bound) //2
        #K만큼 블록으로 나눠지면 한 블록안의 원소개수를 줄여가며 최소 최대값 찾기
        if isValid(A, max_block_cnt, mid):
            upper_bound = mid-1
        #K만큼 블록으로 안나눠지면 한 블록안의 원소개수 늘리기
        else:
            lower_bound = mid+1
    return lower_bound

---

*참고

https://www.martinkysel.com/codility-minmaxdivision-solution/

Codility ‘MinMaxDivision’ Solution | MartinKysel.com