[leetcode][1675] Minimize Deviation in Array

문제 : leetcode.com/problems/minimize-deviation-in-array/

---

n개의 양의 정수를 가지는 배열이 주어진다.

수가 짝수이면 2로 나눌 수 있고 홀수면 2를 곱할 수 있다. (복수번 적용 가능)

배열의 편차는 두가지 요소의 차이 중 최대 값이다.

구할 수 있는 배열의 편차 중 최소 값을 구하여라.

---

짝수면 감소. 홀수면 증가시킬 수 있다.

짝수를 2로 나누면 짝수 혹은 홀수가 나온다.

하지만 홀수를 2로 곱하면 반드시 짝수가 된다.

즉, 모든 요소들의 최대값들은 그 자신의 수(짝수인 경우)거나 x2한 수(홀수인 경우)이다.

따라서 모든 수들을 먼저 최대값으로 만든 뒤, 최대값을 감소시키면서 배열의 편차의 최소 값을 구한다.

구현은 set을 이용했고, 최대 최소는 set의 가장 뒤, 앞의 값인 것으로 알 수 있다. (set은 정렬되어있다.)

 

N은 nums 배열의 크기. M을 nums 요소들 중 최대값이라 했을 때,

시간복잡도는 O(N logN logM)

---

소스코드

c++ : github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/1675.%20Minimize%20Deviation%20in%20Array.cpp

python : https://github.com/fpdjsns/Algorithm-python/blob/main/leetcode/hard/1675.%20Minimize%20Deviation%20in%20Array.py