1551. Minimum Operations to Make Array Equal
[Minimum Operations to Make Array Equal - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com](https://leetcode.com/problems/minimum-operations-to-make-array-equal/)
정수가 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로 일반화할 수 있다.