[LeetCode] 1838. Frequency of the Most Frequent Element

https://leetcode.com/problems/frequency-of-the-most-frequent-element/description/

Frequency of the Most Frequent Element - LeetCode

leetcode - Frequency of the Most Frequent Element

문제 유형 : 정렬, 투 포인터, 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

요소의 빈도는 배열에서 요소가 등장하는 횟수입니다.

당신은 정수배열 nums와 정수 k를 받습니다.

한 번의 연산으로, 배열 요소를 인덱스로 접근하여 값을 1 증가시킬 수 있습니다.

최대 k번의 연산 횟수로 가능한 최대 요소의 빈도를 반환하시오.

 

풀이

정렬 후 슬라이딩 윈도우를 사용하는 방법이 있다.

정렬 방법에서 두 가지로 갈리는데, 문제의 조건에서 요소로 양수만 나온다고 하므로, 개수 정렬을 통해서 O(N + K)의 속도로 정렬이 가능하다.

또는 평범하게 O(nlogn)의 퀵정렬을 사용할 수 있다.

 

right를 오른쪽으로 한 칸씩 이동시킨다.

오른쪽으로 한 칸 이동시키고, 현재 부분배열의 총합을 업데이트한다. (+= nums[right])

 

그리고, 현재 부분배열의 총합에 k를 더한값이 현재 부분배열의 가장 큰 값(nums[right]) * 현재 부분배열의 크기(right - left + 1)보다 크거나 같아질 때 까지 , 현재 부분배열의 총합에서 현재 부분배열의 가장 작은 값을 뺴고, left를 오른쪽으로 한 칸씩 옮긴다.

이로서 현재 최대값을 target으로 두었을 때 최대한의 요소의 개수를 구할 수 있다.

 

(예를 들면, nums[right]이 7이고, 현재 right - left +1이 5라면, sum + k는 35(7*5)보다 크거나 같아야 하고, 그게 아니라면 left를 1 증가시켜서 맨 왼쪽을 제외시키고, 계속 반복하며 연산한다.)

기존의 최대 요소의 빈도과 비교하여 업데이트한다.

 

순회가 끝나면 최대 요소의 빈도를 반환시킨다.

 

코드

C++

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        const int n = nums.size();

        sort(nums.begin(), nums.end());
        long sum = 0;
        int maxFreq = 0;

        for(int left = 0, right = 0; right < n; right++) {
            sum += nums[right];
            while(sum + k < (long)nums[right] *(right - left + 1)) {
                sum -= nums[left];
                left++;

            }
            maxFreq = max(maxFreq, right - left +1);
        }

        return maxFreq;
    }
};