[프로그래머스] 배열의 길이를 2의 거듭제곱으로 만들기

24년 12월 14일
해결한 문제 갯수: 52

 

문제 설명

 

 

문제 분석

- 주어진 배열 arr의 길이를 2의 거듭제곱으로 만들고, 추가된 공간을 0으로 채우는 문제입니다. 이때 최소한의 0을 추가하여 2의 거듭제곱 길이를 만들어야 합니다.

- 원래 배열의 요소는 그대로 유지합니다. 

 

첫 번째 접근: 반환되는 배열의 길이 계산

function solution(arr) {
    const n = Math.ceil(Math.log(arr.length) / Math.log(2))

    return new Array(Math.pow(2, n)).fill(0).map((el, i) => arr[i] ? arr[i] : el)
}

1. n : 반환되어야 하는 배열의 총 길이

- '2ⁿ = arr.length'를 만족하는 n을 계산해야합니다.

- 먼저 양 변에 로그를 취하여 n을 계산합니다.

- Math.ceill()을 사용해, 값을 반올림합니다. 이는 최소한의 2의 거듭제곱 길이를 보장하기 위함입니다. 

2. 결과값 반환

- Array 생성자를 이용해 길이 n의 새로운 배열을 만들고, 배열을 순회하며 arr[i]의 값 또는 0을 채워줍니다. 

 

두 번째 접근: 불필요한 순회 제거

function solution(arr) {
    const n = Math.ceil(Math.log(arr.length) / Math.log(2))

    //return [...arr, ...new Array(Math.pow(2, n) - arr.length).fill(0)]
    return arr.concat(new Array(Math.pow(2, n) - arr.length).fill(0))

}

개선사항

- 추가해야하는 길이 만큼의 0으로 이루어진 배열을 생성하여 spread syntax로 새로운 배열을 반환했다. 

- concat으로 두 배열을 합칠 수도 있다

 

* Spread Syntax V.S Concat() 

Spread 구문은 다음과 같은 과정으로 동작합니다:

const arr1 = [1, 2, 3];
const arr2 = [4, 5, 6];
const newArr = [...arr1, ...arr2];

1. 새로운 배열을 위한 메모리 공간 할당
2. 각 배열의 모든 요소를 순회하며 개별적으로 복사
3. 각 요소를 새 배열에 순차적으로 배치

 

Concat은 다음과 같이 동작합니다:

const arr1 = [1, 2, 3];
const arr2 = [4, 5, 6];
const newArr = arr1.concat(arr2);

1. 새로운 배열을 위한 메모리 공간 할당
2. 내부적으로 최적화된 방식으로 배열 블록 단위 복사
3. 메모리 블록 단위의 효율적인 연결 작업

 

성능 차이가 발생하는 이유

메모리 사용 관점

 

// Spread 구문의 메모리 사용
[빈 공간       ]  // 새 배열 할당
[1, 2, 3]      // 첫 번째 배열 요소들을 개별 복사
[    4, 5, 6]  // 두 번째 배열 요소들을 개별 복사
[1, 2, 3, 4, 5, 6]  // 최종 결과

// Concat의 메모리 사용
[빈 공간       ]  // 새 배열 할당
[1, 2, 3][4, 5, 6]  // 블록 단위로 효율적 복사
[1, 2, 3, 4, 5, 6]  // 최종 결과

 

성능 테스트

// 대규모 배열에서의 성능 비교
const largeArray = new Array(100000).fill(0);

console.time('spread');
const spreadArray = [...largeArray, ...largeArray];
console.timeEnd('spread');

console.time('concat');
const concatArray = largeArray.concat(largeArray);
console.timeEnd('concat');

 

실제 사용시 고려사항

1. 배열 크기에 따른 선택

• 작은 배열 (수백 개 이하의 요소)
  • 성능 차이가 미미함
  • 가독성이 좋은 Spread 구문 권장
• 큰 배열 (수천 개 이상의 요소)
  • Concat이 더 효율적
  • 메모리 사용량 고려 필요

2. 상황별 권장 사용법

// 일반적인 상황 - Spread 구문
const smallArray1 = [1, 2, 3];
const smallArray2 = [4, 5, 6];
const combined = [...smallArray1, ...smallArray2];

// 대용량 데이터 처리 - Concat
const largeArray1 = new Array(10000).fill(0);
const largeArray2 = new Array(10000).fill(1);
const efficientCombined = largeArray1.concat(largeArray2);