[programmers/js] 숫자 블록

숫자 블록

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

문제 설명

그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 1부터 10,000,000까지의 숫자가 적힌 블록을 설치하려고 합니다.

설치 규칙은 다음과 같습니다.

• 블록에 적힌 숫자가 n일 때, 해당 블록은 n 2, n 3, n * 4, ... 위치에 설치된다.
• 이미 설치된 블록이 있다면 덮어쓴다.
• 이런 식으로 1부터 10,000,000까지의 블록을 순서대로 설치한다.

예를 들어, 3까지 설치했을 경우 앞 10칸의 배열은 다음과 같습니다.

[0, 1, 1, 2, 1, 3, 1, 2, 3, 2]

풀이

결국 각 위치 i에 대해 i의 약수 중에서 10,000,000 이하인 가장 큰 약수를 구하는 문제입니다.
(단, i === 1일 때는 예외적으로 0)

function solution(begin, end) {
    // 가장 큰 약수를 구하는 문제
    const answer = [];
    for (let i = begin; i <= end; i++) {
        if (i === 1) {
            answer.push(0);
            continue;
        }
      
        let maxDiv = 1;
        for (let j = 2; j <= Math.sqrt(i); j++) {
            if (i % j === 0) {
                const pair = i / j;
                if (pair <= 10_000_000) {
                    maxDiv = pair;
                    break;
                } else if (j <= 10_000_000) maxDiv = j;
            }
        }
        answer.push(maxDiv)
    }
    return answer;
}