문제 개요
숫자로 구성된 리스트 nums가 주어졌을 때, 이 리스트를 두 그룹 A와 B로 나눌 수 있는지 확인해야 합니다. 이때 다음 두 가지 조건을 동시에 만족해야 합니다.
- A의 원소 합과 B의 원소 합이 서로 같아야 합니다.
- A에 속한 모든 숫자는 B에 속한 모든 숫자보다 엄격하게 작아야 합니다.
예를 들어 입력이 nums = [3, 4, 5, 12]라면 결과는 True입니다. A = [3, 4, 5], B = [12]로 나누면 두 그룹의 합이 각각 12로 동일하고, A의 모든 원소(3, 4, 5)는 B의 원소(12)보다 작기 때문입니다.
해결 접근 방법
이 문제는 정렬과 누적합(prefix sum)을 활용하면 효율적으로 해결할 수 있습니다. 리스트를 오름차순으로 정렬한 뒤, 값이 같은 원소들을 하나의 묶음으로 한꺼번에 처리하면서 경계 지점마다 누적합이 전체 합의 절반과 일치하는지 확인합니다. 서로 다른 값 사이의 경계에서 합이 절반과 같다면, 앞부분(A)의 모든 원소는 뒷부분(B)의 모든 원소보다 작다는 조건이 자연스럽게 만족됩니다.
구체적인 단계는 다음과 같습니다.
- 리스트 nums를 오름차순으로 정렬합니다.
- total 변수에 리스트 전체 원소의 합을 저장합니다.
- 누적합 s와 인덱스 i를 각각 0으로 초기화합니다.
- i가 리스트 길이보다 작은 동안 다음을 반복합니다.
- n을 현재 값 nums[i]로 설정합니다.
- i가 범위 내에 있고 nums[i]가 n과 같은 동안 s에 nums[i]를 더하고 i를 1씩 증가시킵니다. 즉, 같은 값을 가진 원소들을 한 그룹으로 묶어 처리합니다.
- s가 total - s와 같다면, 즉 현재까지의 합이 전체 합의 절반이라면 True를 반환합니다.
- 반복이 끝날 때까지 조건을 만족하지 못하면 False를 반환합니다.
예제 코드
class Solution:
def solve(self, nums):
nums.sort()
total = sum(nums)
s = 0
i = 0
while i < len(nums):
n = nums[i]
while i < len(nums) and nums[i] == n:
s += nums[i]
i += 1
if s == total - s:
return True
return False
ob = Solution()
nums = [3, 4, 5, 12]
print(ob.solve(nums))
입력
[3, 4, 5, 12]
출력
True
동작 원리 살펴보기
[3, 4, 5, 12]는 이미 정렬된 상태이며, 전체 합인 total은 24입니다. 먼저 n = 3을 처리하여 s = 3이 되지만, 3 ≠ 21이므로 계속 진행합니다. 다음으로 n = 4를 처리해 s = 7이 되어도 조건을 만족하지 않습니다. 그러나 n = 5까지 처리하면 s = 12가 되고, total - s 역시 12이므로 True가 반환됩니다. 이 시점에서 리스트는 A = [3, 4, 5]와 B = [12]로 나뉘며, 두 그룹의 합이 12로 같고 A의 모든 원소가 B보다 작으므로 문제의 조건을 완벽히 충족합니다.
복잡도 분석
정렬에 O(n log n)의 시간이 소요되고, 이후의 선형 순회는 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 추가로 사용하는 공간은 정렬 과정에 필요한 공간 외에는 상수 수준으로 매우 효율적입니다.