Python으로 1과 2로만 이루어진 배열을 합이 같은 두 부분으로 나눌 수 있는지 확인하는 방법

문제 소개

배열 nums에는 숫자 1과 2만 들어 있다고 가정해 봅시다. 이 배열을 두 부분으로 나누었을 때, 각 부분에 포함된 원소의 합이 서로 같아지는지 확인하는 것이 이번 문제의 목표입니다.

예를 들어 입력이 nums = [1, 1, 2, 2, 2]라면 결과는 True입니다. 배열을 [1, 1, 2]와 [2, 2]로 나누면 두 부분의 합이 각각 4로 동일하기 때문입니다.

풀이 전략

이 문제는 복잡한 탐색 없이 몇 가지 조건 검사만으로 해결할 수 있습니다. 먼저 다음 두 값을 계산합니다.

• total : 배열의 모든 원소를 더한 전체 합
• one_count : 배열에서 값이 1인 원소의 개수

이 값을 바탕으로 다음 순서로 판단합니다.

1. 전체 합이 홀수라면 두 부분으로 균등하게 나눌 수 없으므로 False를 반환합니다.
2. 전체 합의 절반(total ÷ 2)이 짝수라면 2만으로 목표 합을 맞출 수 있으므로 True를 반환합니다.
3. 목표 합이 홀수인 경우, 배열에 1이 하나라도 있으면(one_count > 0) 그 1을 활용해 나눌 수 있으므로 True를 반환합니다.
4. 위 조건을 모두 만족하지 않으면 False를 반환합니다.

구현 예제

def solve(nums):
    total = 0
    one_count = 0
    total = sum(nums)
    one_count = nums.count(1)
    if total % 2:
        return False
    if (total // 2) % 2 == 0:
        return True
    if one_count > 0:
        return True
    else:
        return False

nums = [1, 1, 2, 2, 2]
print(solve(nums))

입력

[1, 1, 2, 2, 2]

출력

True

동작 원리 살펴보기

예제 배열 [1, 1, 2, 2, 2]의 전체 합은 8입니다. 우선 8은 짝수이므로 첫 번째 조건을 통과하고, 절반인 4 역시 짝수이므로 즉시 True가 반환됩니다. 실제로 [1, 1, 2]와 [2, 2]로 나누면 각 부분의 합이 4로 같아지는 것을 확인할 수 있습니다.

이 알고리즘은 배열을 한 번만 순회하면 되기 때문에 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.