문제 설명
숫자로 이루어진 리스트 nums와 정수 k가 주어집니다. 여기서 '연산'이란 리스트의 임의의 요소에서 1을 빼는 것을 의미하며, 이 연산은 총 k번까지 수행할 수 있습니다. 우리의 목표는 k번의 연산을 모두 사용한(또는 일부만 사용한) 후, 리스트 내에서 가장 큰 값이 될 수 있는 최솟값, 즉 '최댓값의 최솟값'을 구하는 것입니다.
예를 들어 입력이 nums = [3, 4, 6, 5], k = 6이라면 출력은 3이 됩니다. 4를 한 번, 6을 세 번, 5를 두 번 감소시켜 총 6번의 연산으로 리스트를 [3, 3, 3, 3]으로 만들 수 있기 때문입니다.
접근 방법
이 문제는 탐욕적(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 가장 큰 값부터 시작하여, 현재 최댓값과 같은 값을 가진 요소들을 함께 1씩 낮추는 것입니다. 특정 값으로 모든 요소를 낮추는 데 필요한 연산 횟수가 남은 k보다 크면 더 이상 낮출 수 없으므로 현재 값을 반환합니다.
알고리즘의 단계는 다음과 같습니다:
- 리스트를 내림차순으로 정렬합니다.
i := 0,curr := nums[0]으로 초기화합니다.k > 0인 동안 다음을 반복합니다:i가 리스트 길이보다 작고nums[i]가curr과 같은 동안i를 증가시킵니다. (현재 최댓값과 같은 요소의 개수를 셉니다)- 만약
k >= i라면,k -= i하고curr -= 1합니다. (같은 값을 가진i개의 요소를 각각 1씩 감소) - 그렇지 않으면 남은 연산 횟수로는 더 낮출 수 없으므로
curr을 반환합니다.
- 반복문이 끝나면
curr을 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다:
class Solution: def solve(self, nums, k): nums.sort(reverse=True) i = 0 curr = nums[0] while k > 0: while i < len(nums) and nums[i] == curr: i += 1 if k >= i: k -= i curr -= 1 else: return curr return curr ob = Solution() nums = [3, 4, 6, 5] k = 6 print(ob.solve(nums, k))
입력
[3, 4, 6, 5], 6
출력
3
복잡도 분석
내림차순 정렬에 O(n log n)의 시간이 소요되며, 이후 메인 반복문은 각 실행마다 curr을 1씩 감소시키므로 최대 O(k)번 실행됩니다. 따라서 전체 시간 복잡도는 O(n log n + k)입니다. 공간 복잡도는 정렬에 추가 공간이 필요 없으므로 O(1)입니다.