[LeetCode] 2779. Maximum Beauty of an Array After Applying Operation

https://leetcode.com/problems/maximum-beauty-of-an-array-after-applying-operation/description/

leetcode - Maximum Beauty of an Array After Applying Operation

문제 유형: 정렬, 슬라이딩 윈도우

문제 난이도: Medium

 

문제

You are given a 0-indexed array nums and a non-negative integer k.

In one operation, you can do the following:

• Choose an index i that hasn't been chosen before from the range [0, nums.length - 1].
• Replace nums[i] with any integer from the range [nums[i] - k, nums[i] + k].

The beauty of the array is the length of the longest subsequence consisting of equal elements.

Return the maximum possible beauty of the array nums after applying the operation any number of times.

Note that you can apply the operation to each index only once.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.

 

정수 배열 nums와 정수 k를 받는다.

한 번의 연산으로, 당신은 연산된 적 없는 요소에다가 절대값 k만큼 빼거나 더할 수 있습니다.

 

연산을 이용해서 만들 수 있는 같은 수로만 된 부분수열의 최대 길이를 구하시오.

 

풀이

정렬과 슬라이딩 윈도우를 이용해서 풀 수 있다.

가장 작은 요소와 가장 큰 요소의 차이가 2*k까지는 괜찮다는 의미이다. 중앙값으로 통일한다고 가정했을 때 말이다.

그러고, subsequence이므로, 중간의 요소를 생략할 수 있다는 것에다가, 어차피 최종 값은 모두 똑같은 요소로 바뀔 것이니 정렬 후 최대요소 - 최소요소가 2*k이하가 되도록 슬라이딩 윈도우를 만들고 밀어나가면서 최대 크기를 갱신하면 된다는 의미이다.

 

코드

C++

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();

        int ans = 0;
        int j = 0;
        for(int i = 0; i < n; ++i) {
            while(j < i && nums[j] + 2*k < nums[i]) j++;
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};