[LeetCode] 2009. Minimum Number of Operations to Make Array Continuous

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/description/

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 배열 / 정렬 / 슬라이딩 윈도우

문제 난이도 : Hard

 

문제

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if bothㅇof the following conditions are fulfilled:

• All elements in nums are unique.
• The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make nums continuous.

 

정수 배열 nums가 주어진다. 배열의 값이 중복이 없고 최대 값과 최소 값의 차가 nums.length-1일때, 연속적인 배열이라고 한다.

주어질 배열이 연속적으로 될 때 까지 필요한 연산 횟수를 반환하시오.

 

풀이

정수 배열을 정렬하고, 중복 제거를 해준다.

반복문으로 요소를 선택하며 다음을 반복한다

• 현재 값과 현재 값에 배열 크기를 더한 값 사이에 위치한 유일한 값들의 인덱스를 찾기다.
• 배열의 크기에서 해당 인덱스의 차이를 구하여 최소 작업 횟수를 업데이트.

최소 작업 횟수를 반환해주면 된다.

 

코드

C++

 

class Solution {
public:
    int minOperations(std::vector<int>& nums) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        const int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> uniques(nums.begin(), unique(nums.begin(), nums.end()));
        int ans = INT_MAX;

        for (int i = 0; i < uniques.size(); ++i) {
            int s = uniques[i];
            int e = s + n - 1;
            const auto it = upper_bound(uniques.begin(), uniques.end(), e);

            int idx = distance(uniques.begin(), it);
            ans = min(ans, n - (idx - i));
        }
        return ans;
    }
};