1551. Minimum Operations to Make Array Equal

Minimum Operations to Make Array Equal - LeetCode

정수가 N이 주어진다.

1부터 시작하는 홀수 N개의 배열 arr에 대해서 아래 연산 법을 사용할 수 있다.

• 연산 법
  • len를 arr의 길이, 0 <= x, y <= len-1이라고 한다면
  • arr [x]의 값에서 1을 빼고 arr [y]의 값에 1을 더한다.

위 연산을 이용해서 arr의 모든 정수를 같은 수로 바꾸는 최소 연산 횟수를 구하는 문제다.

 

1. 반복문

class Solution:
    def minOperations(self, n: int) -> int:
        answer = 0

        for i in range(1, n, 2):
            answer += (n - i)

        return answer

이 연산은 대칭으로 이루어지는 것이 최소 연산 횟수를 만들 것이라고 직감적으로 알 수 있다.

그러니깐 arr [x]의 값을 +1 하고, arr [len-1-x]의 값을 -1 하는 연산을 arr의 중간값까지 수행하면 된다.

 

홀수, 짝수의 경우를 나누어서 생각해볼 수 있다.

 

홀수인 경우

• n = 7이라면 arr = [1, 3, 5, 7, 9, 11, 13]이다.
• 왼쪽, 오른쪽 대칭으로 +1, -1을 할 수 있기 때문에 중간 값인 7을 기준으로 1부터 7 전까지인 5까지 탐색하면서 그 차이를 더하면 된다.
• (7-1) + (7-3) + (7-5) = 6+4+2 = 2+4+6 = 12

짝수인 경우

• n = 6이라면 arr = [1, 3, 5, 7, 9, 11]이다.
• 이번에는 짝수여서 중간값이 없이 때문에 중간값 근처의 5와 7의 사이인 6이 중간값이 된다.
• 홀수와 동일하게 연산해주면 결과를 얻을 수 있다.
• (6-1) + (6-3) + (6-5) = 5+3+1 = 1+3+5 = 9

결국 중간 값은 입력되는 n과 항상 같기 때문에 1부터 n까지 2씩 증가시키면서 반복문을 돌아 그 차를 더해주면 원하는 답을 얻을 수 있다.

 

2. 최적화

class Solution:
    def minOperations(self, n: int) -> int:
        
        return n * n // 4

1번 풀이보다 시간이 1/2배로 줄었다

이 문제는 수의 성질을 이용하면 O(1)로 해결할 수 있는 문제다.

 

홀수인 경우

• n = 7이라면 arr = [1, 3, 5, 7, 9, 11, 13]이다.
• 결국 더해야 하는 값은 6 + 4 + 2 = 2+ 4 +6이다.
• 2+ 4+ 6 = 2(1 + 2 + 3)이다.
• 한편 n = 7 = 2 * 3 +1이다.
• n = 2k + 1로 일반화시킨다면 우리가 구해야 하는 2(1 +2 +3) = 2(1 + 2 +.... + k) = 2 * ( k * (k+1) / 2) = k* (k+1)이 된다.
  • 1부터 k까지 1씩 증가하는 자연수의 값의 합은 k * (k+1) / 2 다.
• 여기서 n = 2k+1을 k에 대한 식으로 바꾸면 k = (n-1)/2이다.
• 구한 k를 k(k+1)에 대입해 n에 대해서 풀어내면 (n*n-1)/ 4 가 나온다.

짝수인 경우

• n = 6이라면 arr = [1, 3, 5, 7, 9, 11]이다.
• 결국 더해야 하는 값은 5 + 3 +1 = 1+3+5이다.
• 한편 n = 6 = 2*3이다.
• n = 2k로 일반화시키면 우리가 구해야 하는 1+3+5 = k * k가 된다.
  • 1을 포함해서 k개의 홀수를 더한 합은 k*k 다.
• 여기서 n = 2k를 k에 대한 식으로 바꾸면 k = n/2이다.
• 구한 k를 k*k에 대입해 n에 대해서 풀어내면 n* n / 4가 나온다.

결국 홀수일 때 (n*n-1)/ 4, 짝수일 때 n* n / 4를 반환하면 한 번에 문제에서 요구하는 답을 얻을 수 있고, n*n -1을 4로 나누던 n*n을 4로 나누던 컴퓨터에선 기본 연산이 버림이기 때문에 n*n/4로 일반화할 수 있다.