[Level.0] 배열의 길이를 2의 거듭제곱으로 만들기

문제 설명: 정수 배열 arr이 매개변수로 주어집니다. arr의 길이가 2의 정수 거듭제곱이 되도록 arr 뒤에 정수 0을 추가하려고 합니다. arr에 최소한의 개수로 0을 추가한 배열을 return 하는 solution 함수를 작성해 주세요.

제한사항

• 1 ≤ arr의 길이 ≤ 1,000
• 1 ≤ arr의 원소 ≤ 1,000

문제 해결

def solution(arr):
    if len(arr) & (len(arr) - 1) == 0:
        return arr
    cnt = 1
    while cnt < len(arr):
        cnt <<= 1
    return arr + [0] * (cnt - len(arr))

 

주석: 현재 배열의 길이가 2의 거듭제곱인지 비트 연산(n & (n-1))으로 확인하여 조건 미충족 시 비트 시프트 연산(<<)을 통해 현재 길이보다 큰 최소 단위의 2의 거듭제곱 값을 계산하고 부족한 만큼 0을 채워 반환한다.

 

비트 연산의 마법 (n & (n-1))

• 2의 거듭제곱은 이진수로 나타냈을 때 딱 하나의 비트만 1이다 (예: 8 = 1000₂).
• 여기서 1을 빼면 그 아래 비트들이 모두 1이 된다 (예: 7 = 0111₂).
• 둘을 & 연산하면 결과가 반드시 0이 되는 원리를 이용한 매우 빠른 검사법이다.