파이썬으로 k번 연산 후 요소의 최대 빈도 찾기 — 슬라이딩 윈도우 알고리즘

문제 이해하기

배열 nums와 정수 k가 주어졌다고 가정해 봅시다. 한 번의 연산에서는 nums의 인덱스를 하나 선택하여 해당 위치의 요소를 1만큼 증가시킬 수 있습니다. 우리의 목표는 최대 k번의 연산을 수행한 후 얻을 수 있는 특정 요소의 최대 빈도(maximum frequency)를 구하는 것입니다.

예를 들어, nums = [8, 3, 6], k = 9인 경우를 살펴보겠습니다. 값 3을 5번 증가시키고, 값 6을 2번 증가시키면 배열이 [8, 8, 8]이 됩니다. 총 7번의 연산으로 세 요소가 모두 같아지므로, 이 경우 최대 빈도는 3입니다.

접근 방법: 정렬 + 슬라이딩 윈도우

이 문제는 배열을 먼저 정렬한 뒤, 슬라이딩 윈도우(sliding window) 기법을 적용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 윈도우 내의 모든 요소를 윈도우의 최댓값으로 맞추는 데 필요한 연산 횟수를 추적하는 것입니다.

알고리즘 단계

• 배열 nums를 오름차순으로 정렬합니다.
• left := 0, right := 1로 초기화합니다.
• right가 nums의 크기보다 작은 동안 다음을 반복합니다.
  • k에서 (nums[right] − nums[right−1]) × (right − left) 값을 뺍니다. 이는 left부터 right까지의 모든 요소를 nums[right]로 올리는 데 필요한 추가 연산 횟수입니다.
  • k가 음수가 되면(즉, 남은 연산 횟수를 초과하면), k에 nums[right] − nums[left]를 더해 되돌리고 left를 1 증가시켜 윈도우를 축소합니다.
  • right를 1 증가시킵니다.
• 반복이 종료되면 right − left를 반환합니다. 이것이 가능한 최대 빈도입니다.

예제 코드

다음 파이썬 구현을 통해 위 알고리즘을 더 잘 이해할 수 있습니다.

def solve(nums, k):
   nums.sort()
   left = 0
   right = 1

   while right < len(nums):
      k -= (nums[right] - nums[right-1]) * (right - left)

      if k < 0:
         k += nums[right] - nums[left]
         left += 1

      right += 1

   return right - left

nums = [8,3,6]
k = 9
print(solve(nums, k))

입력

[8,3,6], 9

출력

3

마무리

이 알고리즘은 정렬에 O(n log n), 슬라이딩 윈도우 순회에 O(n)의 시간 복잡도를 가지므로 전체적으로 O(n log n)에 해결됩니다. 각 요소를 개별적으로 확인하는 완전 탐색 방식보다 훨씬 효율적이며, 배열이 클 때도 안정적인 성능을 보장합니다.