23.02.24. 풀었던 문제들

리트코드 daily challenge - 1675. Minimize Deviation in Array

 주어진 array에서 짝수는 2로 나눌 수 있고, 홀수는 2배할 수 있을 때, [최대값 - 최소값]의 결과를 최소화하는 문제.

 이것저것 접근하다가 다음과 같이 접근했다.

• 홀수를 2배하면 짝수가 되기 때문에 모든 경우의 수에서 수를 2배로 하는 것은 단 1번이다.(더 이상 커질 수 없다.)
• 나누는 것은 홀수가 될 때 까지 나눌 수 있다.
• 이것에 착안해서 한쪽방향으로만 연산하고자 했다.

 증명은 다음과 같다.

deviation을 줄이기 위해서는 max값을 줄이거나, min값을 늘려야 한다.
모든 홀수를 2배로 해버린다면, min값을 더 늘일 수 없다.
따라서 max값을 줄이는 연산만 남게 된다.
max값을 줄일 수 있을 때까지 줄이면 그것이 min deviatino이다.
 - 홀수에 2를 곱했으며, 어차피 2로 나누면 원래 수로 돌아온다. 필요 시 다시 홀수가 될 것이다.

 

 코드는 다음과 같다.

// runtime 352ms (beats 84.75%)
// memory 89MB (beats 43.22%)

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        set<int> s;
        for(int num : nums){
            s.insert(num & 1 ? num * 2 : num);
        }

        if(s.size() == 1) return 0;
    
        int answer = *s.rbegin() - *s.begin();
        while(!(*s.rbegin() & 1)){
            int last = *s.rbegin();
            s.erase(last);
            s.insert(last / 2);
            if(s.size() == 1) return 0;
            answer = min(answer, *s.rbegin() - *s.begin());
        }
        return answer;
    }
};

 

 시간복잡도는 O(n * logm * logn)이다. set에서 element를 넣고, 꺼내는 데 O(logn)이 걸리며, 어떤 element를 더 이상 줄일 수 없을 때까지 m번 연산한다고 했을 때, 이건 약 30이다.(2의 거듭제곱을 약 30번 줄일 수 있음) worst case 모든 element에 대해 이 연산을 할 수 있기 때문에 O(n * logm * logn)이다. 사실상 logm이 worst 30이기 때문에 O(nlogn)이다.

 공간복잡도는 O(n)이다. set에 n만큼 들어가기 때문.