[프로그래머스] 숫자 블록 - Java

숫자 블록(Lv2)

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

프로그래머스

 

 

 

제한 사항

• 1 ≤ begin ≤ end ≤ 1,000,000,000
• end - begin ≤ 5,000

 

풀이

이번 문제는 자기 자신을 제외한 것중 가장 큰 약수를 구해서 해결했다.
특히, 문제 조건 중, 1~10,000,000인 숫자 블록만 사용한다 했으므로, 이것을 처리하는 것이 포인트였다.

약수를 구하는 것은 제곱근을 이용해서 풀었다.
예를 들어, 36의 제곱근은 6이고, 1~6까지의 숫자를 이용해서 36과 나누어 떨어진다면 36/나누어 떨어진 숫자 또한 약수일 것이기 때문이다. 즉, 36의 약수인 2가 나왔으면, 36/2인 18도 약수가 되는 것이다.

 

 

전체 Code

class Solution {
    public int[] solution(long begin, long end) {
        int s = (int) begin;
        int e = (int) end;
        int[] answer = new int[e-s+1];
        // 약수 중 자기 자신을 제외하고 가장 큰 수
        int idx=0;
        for(int i=s; i<=e; i++){
        
        	// i가 1인 경우 처리
            if(i==1) {
                answer[idx++]=0;
                continue;
            }
            int max=1;
            
            // 자기 자신을 제외하기 위해 j=2 부터 시작
            for(int j=2; j*j<=i; j++){
                if(i%j==0){
                    max=Math.max(max,j);
                    // 최대가 10,000,000 이므로 그 이내의 것만 처리
                    if(j != i/j && i/j<=10000000){
                        max=Math.max(max,i/j);
                    }
                }
            }
            answer[idx++] = max;
        }
        return answer;
    }
}