[LeetCode] Maximum Frequency of an Element After Performing Operations II

https://leetcode.com/problems/maximum-frequency-of-an-element-after-performing-operations-ii/description/?envType=daily-question&envId=2025-10-22

leetcode - Maximum Freqency of an Element After Performing Operations II

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

문제 난이도: Hard

 

문제

You are given an integer array nums and two integers k and numOperations.

You must perform an operation numOperations times on nums, where in each operation you:

• Select an index i that was not selected in any previous operations.
• Add an integer in the range [-k, k] to nums[i].

Return the maximum possible frequency of any element in nums after performing the operations.

 

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

당신은 반드시 numOperations번 만큼 연산을 해야 합니다.

연산은 이전에 골라진 적 없는 인덱스를 하나 골라서, 그 수에 [-k, k]의 수를 nums[i]에 더하는 것입니다.

 

연산을 적용하고 난 후, 가능한 수의 최대 빈도수를 구하시오.

 

풀이

우선, 수와 k의 범위상, 모든 후보 수를 다 탐색할 수 는 없다.

대신, 각 고유한 숫자와 그에 k를 더하고 난 값들을 후보로 추가하면 어떨까?

그 정도는 고려할 만 하다.

 

우선, {number, freq}꼴의 parr 배열을 만들어준다.

그 뒤, prev_cand배열에는 {number, freq}뿐만 아니라, {number + k, freq}들도 추가해준다.

다시 정렬하고 같은 number를 가지는 요소들은 병합시킨다. 이 배열을 candidates라고 하자.

 

이제, candidates의 각 number를 기준으로 하여, number - k, number + k로 각각 이진탐색을 정렬된 nums에서 해준다.

그러면, number를 중심으로 최대 +-k의 범위가 구성된다. 이 범위 내의 수들 중, freq를 지우면, 연산으로 number를 만들 수 있는 수의 개수가 된다. 그러나, 이들은 numOperations를 넘을 수는 없다.

그리고, 이렇게 얻을 수 있는 수의 개수와 freq를 더하여 새로운 정답 후보를 구할 수 있다.

이를 매번 업데이트해준다.

 

최종적으로 남아있는 ans에는 정답이 담겨있다.

 

코드

C++

using ll = long long;

class Solution {
 public:
  int maxFrequency(vector<int>& nums, int k, int numOperations) {
    ll n = nums.size();
    ll ans = 0;
    sort(nums.begin(), nums.end());

    vector<pair<int, int>> parr;
    for (int i = 0; i < n; i++) {
      int j = i;
      while (j < n && nums[j] == nums[i]) {
        j++;
      }
      int cnt = j - i;
      parr.emplace_back(nums[i], cnt);

      i = j - 1;
    }

    vector<pair<ll, ll>> prev_cand;
    for (int i = 0; i < parr.size(); i++) {
      prev_cand.emplace_back(parr[i].first, parr[i].second);
      prev_cand.emplace_back(parr[i].first + k, 0);
    }
    sort(prev_cand.begin(), prev_cand.end());
    vector<pair<ll, ll>> candidates;
    for (int i = 0; i < prev_cand.size(); i++) {
      if (i + 1 < prev_cand.size() &&
          prev_cand[i].first == prev_cand[i + 1].first) {
        candidates.emplace_back(prev_cand[i].first,
                                prev_cand[i].second + prev_cand[i + 1].second);
        i++;
      } else {
        candidates.emplace_back(prev_cand[i].first, prev_cand[i].second);
      }
    }

    for (int i = 0; i < candidates.size(); i++) {
      ll curr = candidates[i].first;
      ll cnt = candidates[i].second;
      ll l = lower_bound(nums.begin(), nums.end(), curr - k) - nums.begin();
      ll r = upper_bound(nums.begin(), nums.end(), curr + k) - nums.begin();

      ll x = min((ll)numOperations, r - l - cnt) + cnt;
      ans = max(ans, x);
    }

    return ans;
  }
};

 

Go

type Pair struct {
	first  int64
	second int64
}

func maxFrequency(nums []int, k int, numOperations int) int {
	sort.Ints(nums)
	parr := make([]Pair, 0)
	for i := 0; i < len(nums); i++ {
		j := i
		for j < len(nums) && nums[i] == nums[j] {
			j++
		}
		cnt := int64(j - i)
		parr = append(parr, Pair{int64(nums[i]), cnt})
		i = j - 1
	}

	prevCand := make([]Pair, 0)
	for i := 0; i < len(parr); i++ {
		prevCand = append(prevCand, parr[i])
		prevCand = append(prevCand, Pair{parr[i].first + int64(k), 0})
	}

	sort.Slice(prevCand, func(i, j int) bool {
		if prevCand[i].first == prevCand[j].first {
			return prevCand[i].second < prevCand[j].second
		}
		return prevCand[i].first < prevCand[j].first
	})

	candidates := make([]Pair, 0)
	for i := 0; i < len(prevCand); i++ {
		if i+1 < len(prevCand) && prevCand[i].first == prevCand[i+1].first {
			candidates = append(candidates, Pair{prevCand[i].first, prevCand[i].second + prevCand[i+1].second})
			i++
		} else {
			candidates = append(candidates, prevCand[i])
		}
	}

	ans := 0
	for i := 0; i < len(candidates); i++ {
		curr := candidates[i].first
		cnt := candidates[i].second

		l := sort.Search(len(nums), func(i int) bool {
			return int64(nums[i]) >= curr-int64(k)
		})
		r := sort.Search(len(nums), func(i int) bool {
			return int64(nums[i]) > curr+int64(k)
		})

		x := min(r-l-int(cnt), numOperations) + int(cnt)
		ans = max(ans, x)
	}

	return ans
}