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

 

난이도: 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.

 

문제 예제

---

Example 1:

Input: nums = [4,6,1,2], k = 2
Output: 3
Explanation: In this example, we apply the following operations:
- Choose index 1, replace it with 4 (from range [4,8]), nums = [4,4,1,2].
- Choose index 3, replace it with 4 (from range [0,4]), nums = [4,4,1,4].
After the applied operations, the beauty of the array nums is 3 (subsequence consisting of indices 0, 1, and 3).
It can be proven that 3 is the maximum possible length we can achieve.

Example 2:

Input: nums = [1,1,1,1], k = 10
Output: 4
Explanation: In this example we dont have to apply any operations.
The beauty of the array nums is 4 (whole array).

 

제한사항

---

• 1 <= nums.length <= 10^5
• 0 <= nums[i], k <= 10^5

 

✏️Solution(솔루션)

---

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        range_list = []
        n = len(nums)

        for num in nums:
            range_list.append((max(0, num-k), num+k))
        
        range_list.sort(key=lambda x:(x[0],x[1]))

        answer = 0

        for i in range(n):
            left, right = i, n - 1 
            while left <= right:
                mid = (left + right) // 2
                if range_list[mid][0] <= range_list[i][1]:
                    left = mid + 1
                else:
                    right = mid - 1

            answer = max(answer, right - i + 1)
        
        return answer

 

문제를 읽다 보니까 다음과 같이 최대한 많이 겹치는 수를 구하면 될 것 같았다.

 

문제 예제에서는 4로 했을 때 3개로 최대가 된다 했는데, 2나 3으로 해도 3개로 최대가 된다.

 

따라서, 각 nums의 요소마다 [num-k, num+k]의 범위를 저장하고, 정렬 시켜주었다.

 

그리고, 이진탐색을 통해 겹치지 않는 구간의 index를 찾았고, 그 index 기반으로 겹치는 수를 구했다.

 

이제 이것이 최대가 되는 값을 찾아 return 하였고, 정답을 맞출 수 있었다.

 

문제를 풀고 나니 시간과 메모리 둘다 효율성이 굉장히 낮게 나왔다.

 

다른 사람들의 풀이를 보니 굳이 이진 탐색을 사용할 필요가 없는 문제인 것 같았다...

 

---

2779. Maximum Beauty of an Array After Applying Operation