큰 수의 법칙

큰 수의 법칙

python 3

def solution(arr, maxLength, dup):
    _sorted = sorted(arr, reverse=True)
    [maxNum, nextMaxNum] = _sorted[0:2]

    # _count = 0
    # result = []
    #
    # result = [nextMaxNum if i % (dup + 1) == 0 else maxNum for i in range(1, maxLength + 1)]

    # return sum(result)

    rowNum = maxLength // (dup + 1)
    restLength = maxLength % (dup + 1)
    rowSum = maxNum * dup + nextMaxNum
    totalSum = rowSum * rowNum + maxNum * restLength

    return totalSum
    
print(solution([2, 4, 5, 4, 6], 8, 3))

주석처리 한 부분은 최적화를 하지 않은 기초적인 풀이법입니다.

[가장 큰 수, 가장 큰 수, ..., 그 다음으로 작은 수, 가장 큰 수, 가장 큰 수, ...] 배열을 만들어, 합하는 것입니다.

하지만 이 문제는 위 배열이 [가장 큰 수 (dup번 반복), 그 다음으로 큰 수] 라는 작은 배열이 반복된다는 점만 알면 최적화할 수 있습니다.

2차원 배열로 표현하자면 다음과 같죠.

[
    [가장큰 수, 가장큰 수, ..., 그 다음으로 큰 수],
    [가장큰 수, 가장큰 수, ..., 그 다음으로 큰 수],
    ...
    [가장 큰 수, ...] // 만약 maxLength 가 dup + 1 로 나누어 떨어지지 않는 경우, 짜투리 배열
]

작은 배열의 길이는 최대 dup + 1이며, 작은 배열의 개수는 총 maxLength // (dup + 1)이 됩니다.

또한 작은 배열의 맨 끝에만 nextMaxNum 이 오므로, 짜투리 배열에는 nextMaxNum이 포함되지 않음은 자명하죠.