• 프로그래머스 배열만들기 2 풀이중 5와 0으로만 구성된 배열을 만들고자 했다.
• 2진수로 5를 곱하여 반복하는 것이 모든 수를 탐색하는 것보다 효율적일 것으로 생각 했지만 바로 구현하지 못하여 포스팅으로 보충해보고자 한다.
  

Integer.BinaryString(int i)

• 가장 쉬운 방법으로 Integer에 i를 주면 i를 2진수로 변경하여 String으로 리턴한다.
• java 내부에서는 전체 길이를 구해서 문자배열로 만들고, 숫자를 2진수로 변환해서 삽입한 후 String으로 변환해서 리턴하는 것으로 확인했다.

풀이문 개선

기본풀이

• 문제에서 주어진 l(최소)과 r(최대)의 범위가 0~100만 이다.
• 시간 복잡도는 O(n) n = r-l으로 최대 100만일 것이다.

import java.util.ArrayList;
class Solution {
    public int[] solution(int l, int r) {
        ArrayList<Integer> answer = new ArrayList<>();

        for (int i = l; i<=r; i++) {
            if(valueChaker(i)) {
                answer.add(i);
            }
        }

        if (answer.isEmpty()) {
            answer.add(-1);
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
    private boolean valueChaker(int n) {
        String str = String.valueOf(n);
        for(char a : str.toCharArray()) {
            if(a != '0' && a !='5') {
                return false;
            }
        }
        return true;
    }
}

변경된 풀이

• 2진수를 활용하면 n을 줄이는 효과가 있을것이다.
• 주어진 최댓값을 활용하여 for문의 반복범위를 정할 수 있다.
• 최솟값은 자릿수보다 한자리 낮은 수에서 시작하도록 했다.

import java.util.ArrayList;
import java.lang.Math;
class Solution {
    public int[] solution(int l, int r) {
        ArrayList<Integer> answer = new ArrayList<>();
        
        int maxExponent = String.valueOf(r).length();
        int minExponent = String.valueOf(l).length();
        
        int max = (int)Math.pow(2, maxExponent);
        int min = (int)Math.pow(2, minExponent);
        
        for (int i = min/2; i<=max; i++) {
            int num = Integer.parseInt(Integer.toBinaryString(i))*5;
            if(l<= num && num <=r) {
                answer.add(num);
            }
        }
        
        if (answer.isEmpty()) {
            answer.add(-1);
        }
                
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}