1. 문제 소개

3346. Maximum Frequency of an Element After Performing Operations I

2. 나의 풀이법

문제를 처음 보았을 때에는 어떻게 푸는지 감이 잘 잡히지 않았다.
그래서 문제의 Editorial과 Solutions의 힌트를 살펴보며 풀었다.

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        maxNum = max(nums) + 1
        count = [0] * maxNum

        for num in nums:
            count[num] += 1
        
        diff = [0] * (maxNum + 2)
        for num in nums:
            left = max(1, num - k)
            right = min(maxNum, num + k)
            diff[left] += 1
            diff[right+1] -= 1

        answer = 0
        cover = 0
        for n in range(1, maxNum):
            cover += diff[n]
            keep = count[n]
            change = cover - keep
            answer = max(answer, keep + min(numOperations, change))
        
        return answer

3. 다른 풀이법

아래의 코드를 참고하여 풀었다.

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOps: int) -> int:
        maxVal = max(nums) + k + 2
        count = [0] * maxVal

        for v in nums:
            count[v] += 1

        for i in range(1, maxVal):
            count[i] += count[i - 1]

        res = 0
        for i in range(maxVal):
            left = max(0, i - k)
            right = min(maxVal - 1, i + k)
            total = count[right] - (count[left - 1] if left else 0)
            freq = count[i] - (count[i - 1] if i else 0)
            res = max(res, freq + min(numOps, total - freq))

        return res

4. 결론

생소한 문제라 접근하기 어려웠다.
유사한 문제로 감을 찾아봐야겠다.