JavaScript에서 배열을 2배 관계로 재정렬할 수 있는지 확인하는 방법

문제 이해

숫자 배열 arr을 첫 번째이자 유일한 인수로 받아 처리하는 JavaScript 함수를 작성해야 합니다.

입력 배열 arr의 길이는 항상 짝수라고 가정합니다.

배열의 요소들을 재배치했을 때 모든 0 <= i < length(arr) / 2 범위에서 arr[2 * i + 1] = 2 * arr[2 * i] 조건을 만족할 수 있는 경우에만 함수는 true를 반환해야 합니다. 다시 말해, 배열의 앞쪽 절반에 있는 각 요소 바로 뒤에는 반드시 그 값의 정확히 2배인 요소가 위치해야 합니다.

예를 들어 함수의 입력이 다음과 같다면:

const arr = [4, -2, 2, -4];

출력은 다음과 같아야 합니다:

const output = true;

출력 설명

요소들을 [-2, -4]와 [2, 4] 두 그룹으로 묶으면 [-2, -4, 2, 4] 또는 [2, 4, -2, -4] 형태로 재정렬할 수 있습니다. 각 쌍에서 두 번째 요소(-4, 4)는 첫 번째 요소(-2, 2)의 정확히 2배이므로 주어진 조건을 충족합니다.

접근 방법

이 문제는 해시 맵(빈도 카운터)과 그리디(greedy) 전략을 활용하면 효율적으로 해결할 수 있습니다.

1. 배열을 순회하며 각 숫자의 등장 횟수를 해시 맵에 기록합니다.
2. 맵의 키 값을 오름차순으로 정렬합니다. 음수는 더 작은 값(절반)부터, 양수는 2배 값부터 먼저 소모해야 올바른 페어링이 가능하기 때문입니다.
3. 키가 음수인 경우 해당 값의 절반(key / 2)이 남아 있는지, 양수인 경우 2배 값(key * 2)이 남아 있는지 확인하며 페어를 하나씩 소모합니다.
4. 페어를 구성할 수 없으면 즉시 false를 반환하고, 모든 요소가 성공적으로 소진되면 true를 반환합니다.

예제 코드

전체 구현 코드는 다음과 같습니다:

const arr = [4, -2, 2, -4];
const canRearrange = (arr = []) => {
   const map = arr.reduce((acc, num) => {
      acc[num] = (acc[num] || 0) + 1
      return acc
   }, {});
   const keys = Object.keys(map)
   .map(key => Number(key))
   .sort((a, b) => a - b)
   for (const key of keys) {
      if (key < 0) {
         while (map[key] > 0) {
            if (map[key / 2] > 0) {
               map[key] -= 1
               map[key / 2] -= 1
            } else {
               return false
            }
         }
      } else {
         while (map[key] > 0) {
            if (map[key * 2] > 0) {
               map[key] -= 1
               map[key * 2] -= 1
            } else {
               return false
            }
         }
      }
   }
   return true
};
console.log(canRearrange(arr));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다:

true

복잡도 분석

시간 복잡도: 키 정렬에 O(n log n)이 소요되며, 이후 각 요소는 최대 한 번씩만 소모되므로 전체 시간 복잡도는 O(n log n)입니다.

공간 복잡도: 빈도 카운터용 해시 맵에 O(n)의 추가 공간이 필요합니다.