(Python3) - LeetCode (Medium) : 2779. Maximum Beauty of an Array After Applying Operation

https://leetcode.com/problems/maximum-beauty-of-an-array-after-applying-operation/description/?envType=daily-question&envId=2024-12-11

sliding window로 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. nums를 오름차순으로 정렬해줍니다.

 

2. left, num_len 선언 후 각각 0과 nums의 길이로 초기화합니다.

 

3. 정답변수 max_length 선언 후 0으로 초기화합니다.

📔 풀이과정

 

• 슬라이딩 윈도우 정의
  슬라이딩 윈도우는 배열에서 특정 구간(범위)을 설정하고, 이 구간을 오른쪽으로 이동(sliding)하며 조건을 만족하는 구간 내 값들을 효율적으로 계산하는 알고리즘입니다.
• 알고리즘 수행 과정
  주어진 문제에서는 numsnumsnums 배열을 정렬한 뒤, $${nums[right]−nums[left]≤2×knums[right] - nums[left] \leq 2 \times knums[right]−nums[left]≤2×k}$$ 조건을 만족하는 범위를 유지합니다.
  • numsnumsnums는 오름차순 정렬되어 있으므로 $${nums[right]≥nums[left]nums[right] \geq nums[left]nums[right]≥nums[left]}$$ 관계를 항상 만족합니다.
  • 조건 확인: $${nums[right]−nums[left]≤2×knums[right] - nums[left] \leq 2 \times knums[right]−nums[left]≤2×k}$$ 일 경우, 범위 내에 있는 값이므로 윈도우를 유지합니다.
  • 조건 초과 시: $${nums[right]−nums[left]>2×knums[right] - nums[left] > 2 \times knums[right]−nums[left]>2×k}$$ 일 경우, 범위를 초과하므로 leftleftleft를 1 증가시켜 윈도우를 축소합니다.
• 구체적인 과정:
  • 윈도우의 길이와 최대값 갱신
    • 현재 윈도우의 길이는 right−left+1right - left + 1right−left+1로 계산됩니다.
    • 이를 max_lengthmax\_lengthmax_length와 비교하여 최댓값을 갱신합니다.
  • 시간 복잡도
    • numsnumsnums 정렬: O(nlog⁡n)O(n \log n)O(nlogn)
    • 슬라이딩 윈도우 탐색: O(n)O(n)O(n)
    • 전체 시간 복잡도: O(nlog⁡n)O(n \log n)O(nlogn)

 

📔 정답 출력 | 반환

max_length를 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        nums.sort()
        left = 0
        num_len = len(nums)
        max_length = 0
            
        for right in range(num_len):
            if nums[right] - nums[left] > 2 * k:
                left += 1
            max_length = max(max_length, right - left + 1)
        return max_length

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.