프로그래머스 - 연습문제 - 숫자 블록

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

프로그래머스

---

문제 설명

그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 하였습니다. 숫자 블록을 설치하는 규칙은 다음과 같습니다.

블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n * 2번째 위치에 설치합니다. 그 다음은 n * 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.

블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치합니다. 예를 들어 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 함수를 완성해 주세요.

---

제한 사항

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

---

입출력 예제

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

---

풀이

대략적으로 어떻게 풀어야할지 느낌은 왔지만 결국 해결하지 못해 다른 사람의 코드를 보고 개선한 코드에 이해한 바를 주석으로 남긴다.

핵심 내용은 제곱근은 자신을 나눌 수 있는 수들의 중간 지점에 위치하는 수이기에 2부터 제곱근까지만 확인하게 하면 된다는 것, 지금 확인하는 값과 나누고자 하는 값의 나머지 몫이 10,000,000 이하라면 그 값이 지금 확인하는 값을 나눌 수 있는 최대값이기에 더 이상 구할 필요 없이 바로 answer에 넣어주면 된다는 것이다.

---

코드

class Solution {
    public int[] solution(long begin, long end) {
        int size = (int) (end - begin) + 1;
        int[] answer = new int[size];
        
        // begin부터 end까지 값들을 살피며 해당 값을 나눌 수 있는 최대 값을 구한다.
        for(int i = (int) begin, idx = 0; i <= end; i++) {
            answer[idx++] = getMaxDivider(i);
        }
        
        return answer;
    }
    
    public static int getMaxDivider(int num) {
        // 만약에 1번 자리가 들어올 경우 무조건 0을 반환
        if(num == 1) return 0;
        
        // 지금 보고 있는 num을 나눌 수 있는 최대값을 기록하는 max
        int max = 0;
        
        // 제곱근은 자기 자신을 나눌 수 있는 수의 절반이기에 2부터 제곱근까지 확인
        for(int i = 2; i <= Math.sqrt(num); i++) {
            // 나눠지는 수를 확인해서 해당 값을 max에 기록
            if(num % i == 0) {
                max = i;
                // 만약에 나눠진 몫이 블록의 최대 값인 10,000,000보다 작으면 해당 몫이 자신을 나눌 수 있는 최대값이기에 이를 반환
                if(num / i <= 10000000) return num / i;
            }
        }
        
        // 나눈 몫들 중에 10,000,000보다 작은 수가 없었던 경우 찾아낸 자신을 나눌 수 있는 최대값인 max를 반환
        if(max != 0) {
            return max;
        }
        
        // 만약 자신이 소수라 나눌 수 있는 수가 없었던 경우 1을 반환
        return 1;
    }
}