Skip to main content

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

https://school.programmers.co.kr/learn/courses/30/lessons/181857

  • 정수 배열 arr이 매개변수로 주어진다.
  • arr의 길이가 2의 정수 거듭제곱이 되도록 arr 뒤에 정수 0을 추가하려고 한다.
  • arr에 최소한의 개수로 0을 추가한 배열을 return
  • 1 ≤ arr의 길이 ≤ 1,000
  • 1 ≤ arr의 원소 ≤ 1,000

정답코드

import java.util.*;

class Solution {
    public int[] solution(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }
        
        // 리스트 크기가 2의 거듭제곱이 될 때까지 0 추가
        while (!isPowerOfTwo(list.size())) {
            list.add(0);
        }
        // ArrayList → arr[]
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    
    // 2의 거듭제곱인지 확인하는 메서드
    private boolean isPowerOfTwo(int n) {
        return (n & (n - 1)) == 0;
    }
}
  • 배열을 리스트로 변환해서 길이를 동적으로 늘림
  • 현재 배열(또는 리스트)의 길이가 2의 거듭제곱인지 확인
  • 아니라면 0을 추가
  • 만족할 때까지 반복!

어려웠던 부분은 2의 거듭제곱인지 확인하는 메서드 쓰는 부분, 리스트 크기가 2의 거듭제곱이 될 때까지 0 추가하는 while문 조건 쓰는 법이다. 참고로 ArrayList는length가 아니라 size()메서드를 쓴다.

✅ 2의 거듭제곱 판별 방법
private boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}
  • 2의 거듭제곱 수는 이진수로 표현했을 때 1비트만 켜져 있음
    예:
    2 → 10,
    4 → 100,
    8 → 1000
  • n - 1은 해당 자릿수보다 하나 낮은 값이니까, n & (n - 1)의 결과는 항상 0이 됨!

프로그래머스에서 좋아요 많이 받은 코드 (장재훈 외 56명)

import java.util.*;

class Solution {
    public int[] solution(int[] arr) {
        int length = 1;

        while (length < arr.length) {
            length *= 2;
        }

        return Arrays.copyOf(arr, length);
    }
}

참신하게 푼 코드가 있어서 가져와봤다. 배열의 공백을 이용해서 푼 코드이다. 핵심은 Arrays.copyOf 메서드와 while (length < arr.length) 조건이다. 

int length = 1;
  • 초기 길이를 1로 설정한다.
  • 2의 거듭제곱을 점점 키워나가기 위한 시작점이다. (예: 1, 2, 4, 8, 16, 32...)
while (length < arr.length) {
    length *= 2;
}
  • arr의 길이보다 크거나 같은 가장 작은 2의 거듭제곱을 찾기 위한 루프이다.
  • 예를 들어 arr.length == 5라면, 이 루프는 length = 8에서 멈춘다.
  • 배열 크기를 2의 거듭제곱 단위로 패딩하는 목적이다.
return Arrays.copyOf(arr, length);
  • arr을 length 길이로 복사해 새 배열을 만들어 반환한다.
  • 복사된 배열의 앞부분은 arr의 원소로 채워지고, 부족한 부분은 자동으로 0으로 채워진다.
✅ Arrays.copyOf

자바에서 정말 자주 쓰이는 배열 유틸리티 메서드 중 하나인데 기존 배열을 원하는 길이만큼 복사해주는 메서드이다. 복사할 길이가 원래 배열보다 길 경우엔 자동으로 0으로 채워준다. (배열 복사 + 자동으로 0채우기) 다양한 타입을 지원하므로 int[], double[], String[] 등 거의 모든 배열에 사용할 수 있다. → 숫자형은 0, 객체형은 null로 채워진다.

기본 문법 : 

int[] newArr = Arrays.copyOf(기존배열, 복사할길이);
  • 기존배열: 복사하고 싶은 대상 배열
  • 복사할길이: 새 배열의 길이

자주 쓰이는 상황 :

  • 배열 길이를 확장하고 싶을 때
  • 초기 배열을 안전하게 복사하고 원본 손상 없이 다루고 싶을 때
  • 배열 크기를 2의 거듭제곱으로 맞추거나, 고정된 크기로 만들고 싶을 때
예제 1: 길이를 늘리는 경우
int[] arr = {1, 2, 3};
int[] result = Arrays.copyOf(arr, 5);
System.out.println(Arrays.toString(result));

출력값:

[1, 2, 3, 0, 0]
  • arr.length == 3이지만,
  • 5칸짜리로 복사했기 때문에 나머지 2칸은 자동으로 0으로 채워진다.
예제 2: 길이를 줄이는 경우
int[] arr = {1, 2, 3, 4, 5};
int[] result = Arrays.copyOf(arr, 3);
System.out.println(Arrays.toString(result));

출력값:

[1, 2, 3]
  • 복사할 길이가 더 짧으면 앞에서부터 자르고 끝!



Back to top