Programmers - 숫자블록 with JAVA

 

 

 

해결

이 문제는 숫자 범위에 대해 집중을 해야한다.

1부터 천만까지의 숫자를 사용해서 1부터 1억번째 블록중 5000개의 값을 알아내는 것이다.

- 완전탐색으로는 해결하지 못함을 바로 알 수 있다.

- 또한 구하고자하는 블록 값의 약수는 천만을 넘지 못한다.

 

로직

1. 블록의 제곱근을 구한다 

예를 들어 20은 약수 [1, 2, 4, 5, 10, 20] 이 있다. 20의 제곱근은 약 4이다.

이때, 4까지의 수를 가지고 [a, b] -> [1, 20], [2, 10], [4, 5] 를 만들 수 있으니 제곱근까지만 판단을 한다.

2. 2부터 시작해 제곱근까지 해당 수를 나눌 것이고 만약 해당 약수가 천만을 넘어가면 패스한다.

3. 약수 중 가장 큰 값을 구한다.

 

 

 

코드

import java.util.*;
class Solution {
    public List<Long> solution(long begin, long end) {
        List<Long> answer = new ArrayList<>();
        for(long num=begin; num<=end; num++){
            if(num == 1){
                answer.add(0L);
                continue;
            }
            if(num == 2){
                answer.add(1L);
                continue;
            }
            answer.add(find(num));
        }
        return answer;
    }
    public static long find(long num){
        long value = (long)Math.sqrt(num)+1;
        long result = 0;
        for(int now=2; now<=value; now++){
            if(num % now == 0){
                result = Math.max(result, now);
                if(num/now <= 10000000){
                    result = Math.max(result, num/now);   
                }
            }
        }
        if(result == 0){
            return 1L;   
        }
        return result;
    }
}

 

 

 

import java.util.*;
class Solution {
    public List<Long> solution(long begin, long end) {
        List<Long> answer = new ArrayList<>();
        for(long now=begin; now<=end; now++){
            answer.add(find(now));
        }
        return answer;
    }
    public static long find(long now){
        if(now == 1){
            return 0L;
        }
        long answer = 1;
        long value = (long)Math.sqrt(now);
        for(long i=2; i<=value; i++){
            if(now % i == 0){
                answer = Math.max(answer, i);
                if(now/i <= 10000000){
                    answer = Math.max(answer, now/i);   
                }
            }
        }
        return answer;
    }
}