1. 문제 소개

3432. Count Partitions with Even Sum Difference

2. 나의 풀이

문제를 봤을 때에는 배열에 홀수의 개수가 홀짝에 따라 답이 다르다고 생각했고, 그대로 풀었을 때 정답이었다.
그러나 시간복잡도가 $O(n)$이라 그런지 매우 느렸다.

class Solution:
    def countPartitions(self, nums: List[int]) -> int:
        odd = 0                      # 배열 내 홀수 원소의 개수를 셀 변수

        for num in nums:             # nums의 모든 원소를 순회
            if num % 2 == 1:         # num이 홀수이면
               odd += 1              # 홀수 개수 증가

        # 전체 합 S의 짝/홀은 홀수 개수 odd의 짝/홀과 동일하다.
        #   · odd 가 짝수 → S는 짝수
        #   · odd 가 홀수 → S는 홀수
        if odd % 2 == 0:
            # 전체 합이 짝수이면, 어떤 partition i(0..n-2)를 선택하더라도
            #   D = sum(left) - sum(right) = 2L - S 에서
            #   2L는 항상 짝수, S는 짝수 → D도 항상 짝수.
            # 따라서 모든 i가 유효 partition → 개수는 (n - 1).
            return len(nums) - 1
        else:
            # 전체 합이 홀수이면, 어떤 partition i에 대해서도
            #   2L는 짝수, S는 홀수 → D = 2L - S 는 항상 홀수.
            # 즉, 짝수 차이를 만드는 partition은 존재하지 않는다.
            return 0

3. 다른 풀이

결국 전체 합이 홀수냐, 짝수냐가 문제였다.
sum()으로 인해 시간복잡도는 $O(n)$이다.

class Solution:
    def countPartitions(self, a: List[int]) -> int:
        # sum(a) & 1 : 전체 합의 짝/홀 판단
        #   - 0 → 짝수
        #   - 1 → 홀수
        #
        # (len(a) - 1, 0)[parity] 는 튜플 인덱싱을 활용한 조건 선택:
        #   parity = 0 → 반환값 = len(a) - 1
        #   parity = 1 → 반환값 = 0
        return (len(a) - 1, 0)[sum(a) & 1]

4. 마무리

더 어려운 풀이도 풀 수 있기를.