파이썬으로 배열 요소를 재배열해 '두 배 조건'을 만족할 수 있는지 확인하는 방법

문제 개요

배열 nums가 주어졌을 때, 배열의 요소들을 재배열하여 다음 조건을 만족할 수 있는지 확인해야 합니다.

조건: 모든 i에 대해 nums[2*i + 1] = 2 * nums[2*i]가 성립해야 합니다. 즉, 배열을 두 개씩 짝지었을 때 뒤쪽 요소가 항상 앞쪽 요소의 정확히 두 배가 되어야 합니다.

예를 들어 입력이 nums = [8, -4, 4, -8]이라면 출력은 True입니다. 배열을 [-4, -8, 4, 8]로 재배열하면 다음과 같이 조건이 성립합니다.

• i = 0일 때: nums[2*0 + 1] = nums[1] = -8 = 2 × (-4)
• i = 1일 때: nums[2*1 + 1] = nums[3] = 8 = 2 × 4

해결 접근 방법

이 문제는 그리디(Greedy) 기법과 빈도 맵(Frequency Map)을 활용해 효율적으로 해결할 수 있습니다. 절댓값 기준으로 오름차순 정렬한 뒤, 작은 값부터 차례대로 자신의 두 배에 해당하는 짝을 찾아 매칭하는 것이 핵심 아이디어입니다.

1. nums의 각 요소와 그 빈도수를 저장하는 맵(freq)을 생성합니다.
2. 절댓값 기준으로 정렬된 nums의 각 요소를 순회합니다.
3. freq[item]이 0이면 이미 사용된 요소이므로 다음 반복으로 넘어갑니다.
4. freq[2 * item]이 0이면 item의 두 배 짝이 존재하지 않으므로 False를 반환합니다.
5. 짝을 찾았다면 freq[item]과 freq[2 * item]을 각각 1씩 감소시킵니다.
6. 모든 요소를 성공적으로 처리했다면 True를 반환합니다.

절댓값 기준으로 정렬하는 이유는 음수를 올바르게 처리하기 위해서입니다. 예를 들어 -4와 -8이 있을 때 -8은 -4의 두 배이므로, 절댓값이 작은 -4를 먼저 처리해야 올바른 매칭이 가능합니다.

파이썬 구현 예제

다음 구현을 통해 동작 과정을 더 잘 이해할 수 있습니다.

from collections import defaultdict

def solve(nums):
    freq = defaultdict(int)
    for item in nums:
        freq[item] += 1
    for item in sorted(nums, key=abs):
        if freq[item] == 0:
            continue
        if freq[2 * item] == 0:
            return False
        freq[item] -= 1
        freq[2 * item] -= 1
    return True

nums = [8, -4, 4, -8]
print(solve(nums))

실행 결과

입력:

[8, -4, 4, -8]

출력:

True

복잡도 분석

시간 복잡도는 정렬에 O(n log n)이 소요되고, 빈도 계산 및 매칭 과정에는 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 빈도 맵 저장을 위해 O(n)입니다.