2009. Minimum Number of Operations to Make Array Continuous

• 해답을 봐도 이해가 어려웠던 문제.
• array를 정렬할 필요가 있다는 것까지는 알았는데 중복된 숫자에 대한 처리, 불연속인 숫자에 대한 처리를 어떤식으로 해야될지 생각하기 어려웠다.
• 일부 test case에 대해서는 정렬된 array의 이웃한 숫자끼리 비교하여 연속되지 않은 경우를 가려내면 풀리기는 하지만 중복된 숫자가 존재하면 처리가 어려운 부분이 있다.

• 먼저 array를 정렬한 뒤 unique한 element만 남겨둔다.

• 그런 뒤 각 unique한 element 에 대하여 다음과 같이 결과를 계산한다 .
• 를 array의 최소값으로 한다면 array에 들어갈 수 있는 최대 값은 이 된다.
• , 를 기준으로 array를 표현하면 아래와 같다.
• 앞에 있는 숫자들 () 그리고 뒤에 있는 숫자들 () 은 , 사이에 있는 숫자들로 대체되어야만 조건을 만족할 수 있다. 따라서 이 숫자들의 개수가 operation의 수가 된다.
• 앞에 있는 숫자들의 개수는 → it - nums.begin()
• 뒤에 있는 숫자들의 개수는 → N - (upper - nums.begin())
• 참고로 upper bound 이기 때문에 array에 가 없어도 상관 없다.
• 결과적으로 operation의 수는 ops = N - (upper - nums.begin()) + it - nums.begin() = N - (upper - it) 가 된다.
• 이 값 중에 최소값을 찾으면 된다.

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int N = nums.size();
        sort(nums.begin(), nums.end());
        auto numsEnd = unique(nums.begin(), nums.end());
        int result = INT_MAX;
        for (auto it = nums.begin(); it != numsEnd; ++it) {
            int maxNum = *it + N - 1;
            auto upper = upper_bound(it, numsEnd, maxNum);
            int diff = upper - it;
            result = min(result, N - diff);
        }
        return result;
    }
};