숫자 리스트 nums와 정수 k가 주어졌을 때, 리스트에서 정확히 한 개의 요소를 제거하여 나머지 요소들의 평균이 정확히 k가 되도록 할 수 있는지 확인해야 합니다. 이 문제에는 다음과 같은 제약 조건이 있습니다.
- 2 ≤ n ≤ 1,000 (n은 nums 리스트의 요소 개수)
- nums[i] ≤ 1,000,000, k ≤ 1,000,000
예를 들어 입력이 [5,3,2,4,6,10]이고 k = 4라면 결과는 True입니다. 10을 제거하면 나머지 요소들의 평균이 (5+3+2+4+6)/5 = 4가 되어 k와 같아지기 때문입니다.
해결 접근 방식
이 문제는 간단한 수학적 관계를 이용하면 선형 시간에 해결할 수 있습니다. 전체 합을 s라고 할 때, 어떤 요소 x를 제거하면 남은 (n-1)개 요소의 합은 s - x가 됩니다. 이 값이 k × (n-1)과 같다면 조건을 만족하므로, 각 요소에 대해 이 등식이 성립하는지만 확인하면 됩니다.
- s := nums에 있는 모든 요소의 총합
- t := k × (nums의 크기 - 1)
- nums의 각 요소 i에 대해 다음을 반복합니다.
- s - i가 t와 같으면 True를 반환합니다.
- 반복이 끝나도 조건을 만족하는 요소가 없으면 False를 반환합니다.
이 방법의 시간 복잡도는 O(n)으로 매우 효율적입니다.
구현 예제
class Solution:
def solve(self, nums, k):
s = sum(nums)
t = k * (len(nums) - 1)
for i in nums:
if s - i == t:
return True
return False
ob = Solution()
nums = [5, 3, 2, 4, 6, 10]
k = 4
print(ob.solve(nums, k))
입력
[5,3,2,4,6,10], 4
출력
True