프로그래머스 - 숫자 블록

문제

1 ~ 1,000,000,000 의 길이의 도로가 있을 때 1,000,000 까지의 숫자가 적혀있는 블록으로 도로를 채우는 문제이다.

블록을 채울 때의 규칙은 다음과 같다.

블록에 적힌 번호가 n 일 때 , 가장 첫 블록은 n* 2 번째 위치부터 n*3 , n*4  , ... 위치에 설치한다.

기존에 설치된 블록이 있을 때는 기존의 블록을 제거하고 새로운 블록을 집어 넣게 된다.  

 

내 풀이

위의 규칙대로 도로를 블록으로 채우게 되면 도로의 길이에 해당하는 블록은 자기 자신을 제외하고 숫자가 1,000,000 이하인 최대 약수가 되며 최대 약수를 구하는 과정에서 사용한 방법은 약수는 쌍을 이루게 된다는 성질을 이용하였다.

1. 자연수 n의 약수를 d라고 가정하면 n / d 또한 약수가 된다.
2. 제곱근 이상의 약수는 n/d 를 이용하여 구할 수 있다.
3. 제곱근을 넘어가면 이미 계산한 값의 약수 쌍이므로 중복 탐색이 된다.

최대 약수를 구하는 함수

위의 방식을 토대로 구현한 최대 약수를 구하는 함수이다.

천만 이하에서 값을 찾아야 하므로 가장 작은 값부터 탐색을 하여 쌍을 이루는 값이 천만 이하이면 최대 값이라 판단하고 바로 리턴을 하게 하였다. 

const division = (number) => {
    if(number === 1){
        return 0;
    }
    const sqrt = Math.sqrt(number);
    let max_div = 1;
    for(let i = 2 ; i <= sqrt ; i++){
        if(number % i === 0){ //i가 number의 약수인경우
            max_div = i; //max값 초기화
            if(number/i <= 1e7){// 천만 이하인 경우, 약수의 쌍을 이루는 값을 구하는 것이므로 항상 정수임이 보장 된다.
                return number/i;
            }
        }
    }

    return max_div;
}

전체 코드

function solution(begin, end) {
    const answer = [];
    
    const division = (number) => {
        if(number === 1){
            return 0;
        }
        const sqrt = Math.sqrt(number);
        let max_div = 1;
        for(let i = 2 ; i <= sqrt ; i++){
            if(number % i === 0){ //i가 number의 약수인경우
                max_div = i; //max값 초기화
                if(number/i <= 1e7){// 천만 이하인 경우, 약수의 쌍을 이루는 값을 구하는 것이므로 항상 정수임이 보장 된다.
                	return number/i;
            	}
            }
        }
        
        return max_div;
    }        
    
    for(let i = begin ; i <= end  ; i++){
        answer.push(division(i))    
    }

    return answer;
}

 

출처 : 프로그래머스

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12923

프로그래머스