1551. Minimum Operations to Make Array Equal

Solution

시간복잡도: O(1)
알고리즘

수학
풀이설명

수열의 성질만 이해하면 되는 문제입니다. arr의 모든 값을 같게 만들기 위해선 arr의 중앙값을 택할 수 밖에 없는데 주어진 조건에 의하면 arr의 중앙값은 n입니다. 필요한 연산의 횟수는 arr내에서 중앙값보다 작은 모든 각 원소와 중앙값 n의 차이를 모두 합한 것입니다.

반복문을 돌려가며 할 수도 있습니다.
- 예시(Python)
```
class Solution:
    def minOperations(self, n):
        sum = 0
        for x in range(1, n, 2):
            sum += abs(x - n)
        return sum
```
위 소스의 시간복잡도는 O(N)입니다. arr의 규칙성을 이용해 수식으로 풀이할 수도 있습니다. 각 원소마다 필요한 연산횟수의 일반항을 구하면 됩니다. 아래 소스는 수식으로 풀이한 예시고 시간복잡도는 O(1)입니다.

소스코드

C++

class Solution {
public:
    int minOperations(int n) {
        return n * (n/2) - (n/2) * (n/2);
    }
};

Python

class Solution:
    def minOperations(self, n):
        return n * (n//2) - (n//2) * (n//2)