길이가 짝수인 배열 nums가 주어졌다고 가정해 봅시다. 이 배열을 적절히 재배열하여 모든 인덱스 0 <= i < len(nums)/2에 대해 다음 조건을 만족할 수 있는지 확인하는 것이 목표입니다.
nums[2*i + 1] = 2*nums[2*i]
즉, 배열을 [x, 2x] 형태의 쌍들로 완전히 나눌 수 있는지 판별하는 문제입니다. 예를 들어 입력이 nums = [4,-2,2,-4]라면, [-4, -2]와 [2, 4] 두 쌍으로 묶을 수 있으므로 출력은 True가 됩니다.
문제 해결 접근 방법
그리디(Greedy) 방식과 카운터(Counter)를 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 절댓값이 작은 숫자부터 먼저 처리하는 것입니다. 그래야 음수와 양수가 섞여 있어도 올바르게 매칭됩니다.
cnt: nums의 모든 요소와 각각의 빈도수를 저장한 맵(Counter)을 생성합니다.절댓값 기준으로 오름차순 정렬된 cnt의 각 요소 x에 대해 다음을 반복합니다.
만약
cnt[x] > cnt[2 * x]라면, x와 짝을 이룰 두 배 값이 부족한 것이므로 False를 반환합니다.짝이 성립되었다면
cnt[2 * x] -= cnt[x]로 해당 개수만큼 차감하여 사용 처리합니다.
모든 검사를 통과하면 True를 반환합니다.
예제 코드
아래 파이썬 구현을 통해 더 자세히 살펴보겠습니다.
from collections import Counter
def solve(nums):
cnt = Counter(nums)
for x in sorted(cnt, key=abs):
if cnt[x] > cnt[2 * x]:
return False
cnt[2 * x] -= cnt[x]
return True
nums = [4,-2,2,-4]
print(solve(nums))입력
[6,0,8,2,1,5]
출력
True
동작 원리 설명
위 예제에서 입력 배열 [6,0,8,2,1,5]는 다음과 같은 쌍으로 재배열 가능합니다.
- [0, 0] → 0의 두 배는 0
- [1, 2] → 1의 두 배는 2
- [3, 6] → 3의 두 배는 6
- [4, 8] → 4의 두 배는 8
모든 요소가 쌍을 이루므로 결과는 True입니다. 만약 하나라도 짝을 이루지 못하는 요소가 있다면 함수는 False를 반환하게 됩니다. 이 알고리즘의 시간 복잡도는 정렬 과정 때문에 O(n log n), 공간 복잡도는 Counter 저장을 위해 O(n)입니다.