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

입출력 예

입출력 예 설명

• 예제 1번의 arr의 길이는 6입니다. arr의 길이를 2의 정수 거듭제곱으로 만드는 방법은 0을 2개, 10개, 26개,..., 추가하는 방법이 있고 그중 최소한으로 0을 추가하는 방법은 2개를 추가하는 것입니다. 따라서 [1, 2, 3, 4, 5, 6, 0, 0]을 return 합니다.

• 예제 2번의 arr의 길이는 4이고 이미 2의 정수 거듭제곱입니다. 따라서 뒤에 0을 추가하지 않아도 되므로 [58, 172, 746, 89]를 return 합니다.

코드 - 시간 초과 실

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(int[] arr) {
        int arrLength = arr.length;
        int diffLength = 0;
        int pow = 0;
        
        while(true) {
            
            int value = (int) Math.pow(2, pow);
            
            if(arrLength == value) {
                break;
            } else if(arrLength < value) {
                diffLength = value - arrLength;
            } else {
                pow++;
            }
        }
        
        List<Integer> result = Arrays.stream(arr)
            .boxed()
            .collect(Collectors.toList());
        
        
        
        for(int i = 0; i < diffLength; i++) {
            result.add(0);
        }
        
        return result.stream()
            .mapToInt(i->i)
            .toArray();
    }
}

• 빨간줄 while 문이 시간 초과됨

• Math.pow()는 double 반환: 이 메서드는 정수 거듭제곱이 아닌 부동 소수점(실수, double) 연산을 수행하도록 설계되었습니다.

• CPU 비용: CPU는 정수 연산(덧셈, 곱셈, 비트 연산)보다 부동 소수점 연산을 처리하는 데 훨씬 더 많은 시간과 자원을 소모합니다. 이 복잡한 계산을 루프가 돌 때마다 반복하는 것은 엄청난 성능 저하를 초래합니다.

코드 - 비트 연산자를 사용해서 해결

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;

class Solution {

    /**
     * 배열의 길이를 2의 거듭제곱으로 맞추기 위해 0을 채워넣는 메서드 (패딩)
     * @param arr 입력 배열
     * @return 길이가 2의 거듭제곱인 새로운 배열
     */
    public int[] solution(int[] arr) {
        int arrLength = arr.length;
        
        // 1. [해결책 1] Math.pow() 대신 비트 연산으로 2의 거듭제곱 목표 길이 찾기 (최적화)
        // targetLength를 1로 시작하여 arrLength보다 크거나 같아질 때까지 2배씩 곱합니다.
        int targetLength = 1; 
        while (targetLength < arrLength) {
            targetLength <<= 1; // targetLength *= 2 와 동일. 가장 빠르고 효율적입니다.
        }

        int diffLength = targetLength - arrLength; 
        
        // 2. [해결책 2] 안전한 가변 리스트 생성 (컬렉션 안정성 확보)
        // Collectors.toCollection(ArrayList::new)를 사용하여 'add'가 확실하게 가능한 ArrayList를 만듭니다.
        List<Integer> resultList = Arrays.stream(arr)
                                        .boxed()
                                        .collect(Collectors.toCollection(ArrayList::new));

        // 3. 부족한 길이만큼 0 추가 (패딩)
        for (int i = 0; i < diffLength; i++) {
            resultList.add(0);
        }

        // 4. List<Integer>를 int[]로 변환하여 반환
        // mapToInt와 toArray는 깔끔하고 효율적인 방식입니다.
        return resultList.stream()
                         .mapToInt(i -> i)
                         .toArray();
    }
}

💡 비트 연산 코드 동작 원리 설명

int targetLength = 1; // 2의 0승 (2^0)으로 시작
while (targetLength < arrLength) {
    targetLength <<= 1; // targetLength를 2배로 만듭니다. (왼쪽 시프트)
}

• targetLength는 2의 거듭제곱(2n)을 저장할 변수입니다.

• 초기값 1은 20과 같습니다.

• 루프는 현재의 targetLength가 우리가 원하는 길이(arrLength)보다 작을 때만 계속됩니다.

• targetLength가 arrLength를 넘어서거나 같아지면 루프가 종료됩니다.

• << (왼쪽 시프트 연산자): 정수의 모든 비트를 왼쪽으로 이동시킵니다.

• targetLength <<= 1의 의미: targetLength의 모든 2진 비트를 왼쪽으로 1칸 이동시킵니다.

• 수학적 효과: 컴퓨터에서 숫자의 비트를 왼쪽으로 한 칸 이동시키는 것은 그 숫자에 2를 곱하는 것과 정확히 같습니다.