Python으로 숫자 목록에서 합이 홀수가 되는 유효한 쌍의 개수 구하기

양의 정수로 이루어진 리스트 nums가 주어졌을 때, i < j를 만족하는 인덱스 쌍 (i, j) 중에서 nums[i] + nums[j]의 합이 홀수가 되는 유효한 쌍의 개수를 구하는 문제입니다.

예를 들어 입력이 [5, 4, 6]이라면 출력은 2가 됩니다. [5, 4]의 합은 9, [5, 6]의 합은 11로, 두 쌍 모두 합이 홀수이기 때문입니다.

해결 접근 방식

두 수의 합이 홀수가 되려면 반드시 하나는 홀수, 다른 하나는 짝수여야 합니다. 즉, '홀수 + 짝수 = 홀수'라는 성질을 활용하면 다음과 같은 간단한 공식을 도출할 수 있습니다.

• e := nums에서 짝수만 추출하여 만든 리스트
• 정답 = (nums의 전체 길이 − e의 길이) × e의 길이

전체 길이에서 짝수의 개수를 빼면 홀수의 개수가 되고, 홀수 개수와 짝수 개수를 곱하면 가능한 모든 유효한 쌍의 개수가 계산됩니다. 이 방법은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)으로 매우 효율적입니다.

구현 예제

class Solution:
    def solve(self, nums):
        e = [i for i in nums if i % 2 == 0]
        return (len(nums) - len(e)) * len(e)

nums = [5, 4, 6]
ob = Solution()
print(ob.solve(nums))

입력

[5, 4, 6]

출력

2

리스트 컴프리헨션을 사용해 짝수만 필터링한 뒤, 홀수 개수와 짝수 개수를 곱하는 방식으로 문제를 손쉽게 해결할 수 있습니다.