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

문제

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

프로그래머스

문제 분석

[제한 사항]

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

번호가 n 일 경우 n*2, n*3, n*4 ... 위치에 해당 블록을 설치한다.

예를 들면 2번 블록은 4, 6, 8 ... 번 위의 블록에 설치된다.

 

도로에 1부터 10,000,000 까지의 숫자가 적힌 블록들을 위의 규칙대로 설치하고 begin ~ end 까지의 블록 상태를 반환하는 문제이다.

문제 접근

end의 범위가 크기 때문에 모든 블록을 깔고 해당 범위의 블록을 반환하게 되면 시간초과가 날 것이다.

따라서 해당 범위에서 바로 어떤 블록이 깔리는 지를 계산해야 한다.

 

n번 째 타일에는 n을 나눠 나머지가 0인 가장 큰 수가 온다는 규칙을 찾을 수 있다.

예를 들어 10번 째 타일에는 5가 온다. (10 % 5 == 0)

 

여기서 주의할 점이 있는데 블록이 10,000,000 까지만 있다는 것이다.

end 범위보다 작기 때문에 이 부분을 주의해서 조건을 넣어주어야 한다.

코드

import java.util.*;

class Solution {
    public int[] solution(long begin, long end) {
        int[] answer = new int[(int)(end-begin) + 1];
        
        for(long i=begin; i<=end; i++){
            answer[(int)(i-begin)] = (int)maxDivisor(i);
        }
        return answer;
        
    }
    
    public static long maxDivisor(long num){
        int result = 1;

        if(num == 1){
            return 0;
        }

        for(int i=2; i<=Math.sqrt(num); i++){
            if(num % i == 0){
                System.out.println(i);
                if(num / i <= 10000000){
                    result = Math.max(result, (int) (num / i));
                    break;
                }else{
                    result = Math.max(result, i);
                }
            }
        }
        return result;
    }
}