숫자 블록

---

출처 프로그래머스 - 숫자 블록

사용 언어 자바

문제 설명

그렙시에는 0으로 된 도로에 숫자 블록을 설치하기로 하였습니다. 숫자 블록의 규칙은 다음과 같습니다.

블록의 번호가 n 일 때, 가장 처음 블록은 n * 2번째 위치에 설치합니다. 그다음은 n * 3, 그다음은 n * 4, …로 진행합니다.만약 기존에 블록이 깔려있는 자리라면 그 블록을빼고 새로운 블록으로 집어넣습니다.

예를 들어 1번 블록은 2,3,4,5, … 인 위치에 우선 설치합니다. 그다음 2번 블록은 4,6,8,10, … 인 위치에 설치하고, 3번 블록은 6,9,12… 인 위치에 설치합니다.

이렇게 3번 블록까지 설치하고 나면 첫 10개의 블록은 0, 1, 1, 2, 1, 3, 1, 2, 3, 2이됩니다.

그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다.

그렙시의 시장님은 특정 구간의 어떤 블록이 깔려 있는지 알고 싶습니다.

구간을 나타내는 두 수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열(리스트)을 return하는 solution 함수를 완성해 주세요.

제한 사항

• begin, end 는 1 이상 1,000,000,000이하의 자연수 이고, begin는 항상 end보다 작습니다.
• end - begin 의 값은 항상 10,000을 넘지 않습니다.

입출력 예

begin	end	result
1	10	[0, 1, 1, 2, 1, 3, 1, 4, 3, 5]

문제를 제대로 읽는 습관을 들여야한다
블록 번호 * 2부터 시작인걸 몰라 시간을 많이 허비했다

4단계 문제가 end번째 블록까지 하나하나 숫자를 덮어 씌워가며 계산하는 방식으로 풀릴리가 없다
한번에 어떤 숫자인지 알아내야할 것이다

일단 블록 번호 * 2부터 시작이면, n번째 블록의 숫자는 최대 n / 2다
짝수라면 n / 2가 맞지만 홀수는 아니다
홀수 중에서도 소수라면 1이 나와야 한다

자신을 제외한 약수 중에 가장 큰 수가 맞는것 같다
가장 작은 약수로 자신을 나눠서 찾을수 있었고
2부터 n / 2까지 올려가며 찾았지만 실패했다
9의 경우만 봐도 제곱근까지만 탐색해도 된다는걸 알았을텐데

길이가 1,000,000,000인 도로에 10,000,000번 블록까지
놓았다는 부분에 따라 10,000,000까지만 처리해줬고

마지막으로 뭔가 멋지게 begin이 1일 때 첫번째 블록을 처리할 방법을 찾다가
포기하고 삼항연산자로 걸러줬다

제출 답안

import java.util.*;

class Solution {
    
    private final int MAX = 10_000_000;
    
    public int[] solution(long begin, long end) {
        int len = (int) (end - begin) + 1;
        int[] answer = new int[len];
        
        for (int i = 0; i < len; i++) {
            answer[i] = getDivisor((int) begin + i);
        }
        
        answer[0] = begin == 1 ? 0 : answer[0];
        return answer;
    }
    
    private int getDivisor(int n) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if ((n % i == 0) &&
                (n / i <= MAX)) return n / i;
        }
        return 1;
    }
}