파이썬으로 배열의 모든 원소를 동일하게 만드는 최소 연산 횟수 구하기

문제 설명

값 n이 주어지고, 길이가 n인 배열 nums가 있다고 가정해 보겠습니다. 이 배열은 모든 인덱스 i에 대해 arr[i] = (2 * i) + 1로 정의되므로, [1, 3, 5, 7, ...]처럼 홀수로 채워진 형태입니다.

한 번의 연산에서는 0 <= x, y < n을 만족하는 두 인덱스 x와 y를 선택하여 nums[x]에서 1을 빼고 nums[y]에 1을 더할 수 있습니다. 목표는 이러한 연산을 반복해 배열의 모든 원소를 같은 값으로 만드는 것이며, 이때 필요한 최소 연산 횟수를 구해야 합니다.

예시

입력이 n = 4라면 배열은 [1, 3, 5, 7]이 되고, 출력은 4입니다. 연산 과정을 단계별로 살펴보면 다음과 같습니다.

• 첫 번째 연산 후: [2, 3, 5, 6]
• 두 번째 연산 후: [3, 3, 5, 5]
• 세 번째 연산 후: [4, 3, 4, 5]
• 네 번째(마지막) 연산 후: [4, 4, 4, 4]

단 네 번의 연산만으로 모든 원소를 4로 일치시킬 수 있습니다.

접근 방법

이 배열의 평균값은 항상 n입니다. 따라서 n보다 작은 원소들은 부족한 만큼 1씩 증가해야 하고, 한 번의 연산으로 특정 원소에 더할 수 있는 값은 최대 1입니다. 결국 최소 연산 횟수는 배열의 낮은 절반에 속한 원소들의 부족량의 합, 즉 Σ(n − (2i + 1))과 같습니다.

이 아이디어를 바탕으로 다음 단계를 따라 문제를 해결할 수 있습니다.

• ans := 0으로 초기화합니다.
• n이 1이라면 그대로 ans를 반환합니다.
• q := (n // 2) - 1로 설정합니다.
• j := 1로 설정합니다.
• q >= 0인 동안 다음을 반복합니다.
  • ans := ans + (n - j)
  • q := q - 1
  • j := j + 2
• ans를 반환합니다.

구현 예제

def solve(n):
    ans = 0
    if n == 1:
        return ans
    q = (n // 2) - 1
    j = 1
    while q >= 0:
        ans = ans + (n - j)
        q -= 1
        j += 2
    return ans

n = 4
print(solve(n))

입력

4

출력

4

정리

홀수로 구성된 배열을 평균값 n에 맞추는 데 필요한 최소 연산 횟수는, n보다 작은 절반의 원소들이 부족한 양의 합과 같습니다. 위 알고리즘은 O(n) 시간 복잡도 안에 답을 계산하고 추가 공간도 상수 수준만 사용하므로 매우 효율적입니다.