문제 개요
nums라는 이름의 배열이 주어졌을 때, 이 배열 안에 나머지 모든 요소들의 합과 값이 동일한 요소가 존재하는지 확인하는 것이 목표입니다.
예를 들어, 입력이 nums = [3, 2, 10, 4, 1]이라면 출력은 True입니다. 그 이유는 10 = (3 + 2 + 4 + 1)이 성립하기 때문입니다.
핵심 아이디어
이 문제는 간단한 수학적 성질을 이용하면 효율적으로 해결할 수 있습니다.
- 어떤 요소 x가 나머지 요소들의 합과 같다면, 전체 합(total)은 x * 2와 같습니다.
- 따라서 x는 반드시 total / 2여야 하며, total이 홀수라면 조건을 만족하는 요소는 절대 존재할 수 없습니다.
즉, 전체 합을 구한 뒤 그 절반의 값이 배열에 실제로 존재하는지만 확인하면 됩니다.
알고리즘 단계
- freq := 각 숫자의 등장 횟수를 저장할 빈 딕셔너리(맵)
- total := 0으로 초기화
- i를 0부터 len(nums) - 1까지 반복:
- freq[nums[i]]의 개수를 1 증가
- total에 nums[i]를 더함
- 만약 total이 짝수라면:
- freq[total // 2]의 값이 0이 아니라면 True 반환
- 그 외의 경우 False 반환
구현 코드
from collections import defaultdict
def solve(nums):
freq = defaultdict(int)
total = 0
for i in range(len(nums)):
freq[nums[i]] += 1
total += nums[i]
# 전체 합이 짝수인 경우에만 절반 값이 존재할 가능성 있음
if total % 2 == 0:
if freq[total // 2]:
return True
return False
nums = [3, 2, 10, 4, 1]
print(solve(nums))입력
[3, 2, 10, 4, 1]
출력
True
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하여 빈도 맵과 총합을 계산합니다.
- 공간 복잡도: O(n) — 고유한 숫자의 개수만큼 딕셔너리 공간이 필요합니다.
이처럼 브루트포스 방식으로 모든 조합을 검사하는 대신, 전체 합의 절반이 배열에 있는지 한 번의 순회로 확인하면 선형 시간 안에 문제를 해결할 수 있습니다.