문제 개요
숫자로 이루어진 리스트 nums가 주어졌을 때, 모든 요소의 값을 동일하게 만들려고 합니다. 이때 사용할 수 있는 연산은 다음과 같습니다.
연산 정의: 리스트에서 하나의 요소를 선택하고, 나머지 모든 요소의 값을 1씩 증가시킵니다.
목표는 이 연산을 반복해서 모든 요소의 값이 같아지도록 만드는 것이며, 이때 필요한 최소 연산 횟수를 구하는 것입니다.
예시
입력이 [2, 4, 5]라면 출력은 5가 됩니다.
핵심 아이디어
이 문제의 열쇠는 연산을 상대적인 관점에서 바라보는 것입니다. "하나의 요소를 제외한 나머지를 1씩 증가"시키는 연산은, 전체 기준선을 뒤집어 생각하면 "선택되지 않은 하나의 요소를 1씩 감소"시키는 것과 수학적으로 동일합니다.
따라서 모든 요소를 최솟값(min_val)에 맞추기 위해 각 요소가 얼마나 줄어야 하는지 더하면 정답이 됩니다. 최솟값 자체는 더 이상 낮출 수 없으므로, 목표 값은 항상 리스트의 최솟값이 됩니다.
정답 = Σ (num − min(nums))
해결 단계
min_val:= nums의 최솟값s:= 0- nums의 각 num에 대해 반복:
- s := s + (num − min_val)
- s 반환
구현 예제
class Solution:
def solve(self, nums):
min_val = min(nums)
s = 0
for num in nums:
s += num - min_val
return s
ob = Solution()
nums = [2, 4, 5]
print(ob.solve(nums))
입력
[2, 4, 5]
출력
5
복잡도 분석
리스트를 두 번 순회(최솟값 탐색 + 합계 계산)하면 되므로 시간 복잡도는 O(n)이며, 추가 공간은 상수 수준인 O(1)입니다. 매우 효율적인 해법입니다.