파이썬으로 모든 쌍이 '좋은 쌍'인 최대 부분 수열의 크기 구하기

문제 설명

크기가 n인 수열 nums가 주어져 있다고 가정해 봅시다. 이때 수열에서 추출할 수 있는 부분 수열(subsequence) 중, 모든 쌍 (p, q)이 '좋은 쌍(nice pair)'을 이루는 부분 수열의 최대 크기를 구해야 합니다.

두 수가 좋은 쌍이 되려면 아래 조건 중 적어도 하나를 만족해야 합니다.

1. 소수 인수 개수의 홀짝성 일치: p의 서로 다른 소수 인수(distinct prime divisor) 개수가 홀수인지 짝수인지가 q와 같아야 합니다. 예를 들어 18은 2와 3, 두 개의 서로 다른 소수 인수를 가집니다.
2. 약수의 합의 홀짝성 일치: p의 모든 양의 약수를 더한 값이 홀수인지 짝수인지가 q와 같아야 합니다.

예를 들어 입력이 nums = [2, 3, 6, 8]이라면 정답은 3입니다.

예제 이해하기

각 숫자의 특성을 직접 계산해 보면 다음과 같습니다.

여기서 {2, 3, 8}을 선택하면 세 쌍 (2, 3), (2, 8), (3, 8)이 모두 소수 인수 개수의 홀짝성이 '홀수'로 같으므로 좋은 쌍을 이룹니다. 반면 6은 2나 8과 좋은 쌍을 이루지 못하므로 네 숫자 전체를 한 부분 수열에 담을 수 없고, 따라서 최대 크기는 3이 됩니다.

풀이 접근 방법

핵심 아이디어는 각 숫자를 두 가지 기준, 즉 소수 인수 개수의 홀짝성과 약수의 합의 홀짝성으로 분류한 뒤, 같은 분류를 공유하는 숫자들을 묶어주는 것입니다. 단계별로 살펴보겠습니다.

1. n := nums의 크기로 설정하고, 빈 리스트 cnt, total, result를 준비합니다.
2. nums의 각 원소 i에 대해 다음을 수행합니다.
   • 먼저 nums 안에서 소수만 골라 prime 리스트를 만듭니다.
   • i를 나눌 수 있는 소수의 개수를 세어 count에 저장하고, 그 홀짝성에 따라 cnt에 'odd' 또는 'even'을 추가합니다.
   • 1부터 i까지의 모든 약수를 더해 tot에 저장하고, 그 홀짝성에 따라 total에 'odd' 또는 'even'을 추가합니다.
3. 모든 쌍 (i, j)에 대해 cnt[i]와 cnt[j]가 같거나 total[i]와 total[j]가 같으면 해당 숫자들을 result에 추가합니다.
4. result를 집합(set)으로 변환해 중복을 제거한 후, 그 크기를 반환합니다.

파이썬 구현 예제

아래 코드를 통해 더 쉽게 이해할 수 있습니다.

def solve(nums):
    n = len(nums)
    cnt = []
    total = []
    result = []
    for i in nums:
        count = 0
        tot = 0

        # nums에서 소수만 추출
        prime = []
        for j in nums:
            if all(j % k for k in range(2, j)) == True:
                prime.append(j)

        # i의 서로 다른 소수 인수 개수 확인
        for j in prime:
            if i % j == 0:
                count += 1
        if count % 2:
            cnt.append('odd')
        else:
            cnt.append('even')

        # i의 모든 양의 약수의 합 계산
        for j in range(1, i + 1):
            if i % j == 0:
                tot += j

        if tot % 2:
            total.append('odd')
        else:
            total.append('even')

    # 조건을 만족하는 쌍 찾기
    for i in range(n - 1):
        for j in range(i + 1, n):
            if cnt[i] == cnt[j] or total[i] == total[j]:
                result.append(nums[i])
                if j == n - 1:
                    result.append(nums[j])

    result = list(set(result))
    return len(result)

nums = [2, 3, 6, 8]
print(solve(nums))

입력 및 출력

입력:

[2, 3, 6, 8]

출력:

3

마무리 및 성능 개선 팁

이 풀이는 각 숫자에 대해 소수 여부와 약수의 합을 직접 계산하므로 구현이 단순하다는 장점이 있지만, 숫자의 범위가 커지면 실행 시간이 길어질 수 있습니다. 실전에서는 에라토스테네스의 체(sieve of Eratosthenes)로 소수를 미리 구하거나, 제곱근까지만 나눠보는 방식으로 소수 판별과 약수 합 계산 속도를 크게 개선할 수 있습니다. 또한 약수의 합이 홀수가 되려면 해당 수가 완전제곱수이거나 완전제곱수의 2배여야 한다는 성질을 활용하면 판별 과정을 훨씬 단순화할 수 있습니다.