문제 설명
숫자 리스트 nums와 정수 k가 주어집니다. 리스트의 임의의 원소를 1씩 증가시키는 연산을 최대 k번까지 수행할 수 있을 때, 만들어 낼 수 있는 숫자 중 가장 자주 등장하는 값을 구하는 것이 목표입니다. 만약 조건을 만족하는 숫자가 여러 개라면 그중 가장 작은 값을 선택해야 합니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
nums = [1, 0, 0, 0, 8, 8, 8, 8], k = 8
이 경우 출력은 8입니다. 값 1을 7번 증가시켜 8로 만들고, 0 하나를 1로 증가시키면 리스트는 [8, 1, 0, 0, 8, 8, 8, 8]이 되어 8이 총 5번 등장하기 때문입니다.
접근 방법: 슬라이딩 윈도우(투 포인터)
이 문제는 정렬된 배열 위에서 슬라이딩 윈도우 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 리스트를 오름차순으로 정렬하면, 윈도우 안의 모든 원소를 윈도우의 최댓값으로 올리는 데 필요한 총 증가량을 누적 변수
dist로 추적할 수 있습니다. dist가 k를 초과하면 왼쪽 포인터(low)를 이동시켜 윈도우를 축소하고, 초과분만큼 비용을 차감합니다.- 윈도우 크기(
high - low)가 지금까지의 최댓값보다 크면 정답 후보를 갱신합니다.
알고리즘 단계
- 리스트
nums를 정렬합니다. low = 0,high = 0으로 초기화합니다.dist = 0,best = 0,ret = -1로 초기화합니다.high가 리스트 길이보다 작은 동안 다음을 반복합니다.high > 0이고nums[high]가nums[high - 1]과 다르면,dist += (high - low) * (nums[high] - nums[high - 1])로 비용을 갱신합니다.high를 1 증가시킵니다.dist > k인 동안dist -= nums[high - 1] - nums[low]를 수행하고low를 1 증가시킵니다.high - low > best이면best와ret(nums[high - 1])을 갱신합니다.
- 반복이 끝나면
ret을 반환합니다.
예제 코드
class Solution:
def solve(self, nums, k):
nums.sort()
low, high = 0, 0
dist = 0
best = 0
ret = -1
while high < len(nums):
if high > 0 and nums[high] != nums[high - 1]:
dist += (high - low) * (nums[high] - nums[high - 1])
high += 1
while dist > k:
dist -= nums[high - 1] - nums[low]
low += 1
if high - low > best:
best = high - low
ret = nums[high - 1]
return ret
ob = Solution()
nums = [1, 0, 0, 0, 8, 8, 8, 8]
k = 8
print(ob.solve(nums, k))
입력
[1, 0, 0, 0, 8, 8, 8, 8], 8
출력
8
복잡도 분석
- 시간 복잡도: O(n log n) — 정렬에 O(n log n), 이후 투 포인터 탐색은 각 포인터가 최대 n번 이동하므로 O(n)입니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 포인터와 누적 변수만 사용합니다.