링크
https://school.programmers.co.kr/learn/courses/30/lessons/12923
문제
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 함수를 완성하라.
예제로 이해
위와 같이 블럭이 깔리게 되는데, n번 블록에 대해서 다음과 같은 규칙을 만족하게 된다.
n번 블록의 번호 => n의 약수 중 자기 자신을 제외한 최대값
규칙에 따르면 약수를 구해야하는데 약수를 모두 계산할 경우에 너무 큰 숫자의 블록을 계산하게 될 경우에 너무 오랜 시간이 걸릴 수 있다. 따라서 약수 중의 가장 큰 숫자만 구하는 것이 가장 좋은 시간 복잡도를 가질 수 있다.
가장 큰 약수를 구한다고만 생각하면 n을 n-1부터 -1씩 진행하며 나누어 떨어지는지 확인하는 방법이 가장 먼저 떠오르겠지만, 이 방법을 채택할 경우에 너무 오래 걸릴 위험이 있다. 만약 블록 번호가 10억이라면, 당장 약수만 하더라도 5억이므로 반복 횟수만 5억이므로 너무 오랜 시간이 걸린다.
따라서 접근을 다르게 할 필요가 있다.
약수는 제곱근을 제외한다면 항상 어떤 수와 어떤 수의 곱으로 즉, 제곱근을 제외하면 두 숫자가 페어를 이룬다. 즉 1과 n을 제외하면 가장 작은 약수와 가장 큰 약수가 서로 페어를 이루게 된다. 따라서 가장 작은 약수를 구하면 가장 큰 약수를 구할 수가 있다.
코드
function solution(begin, end) {
let result = new Array(end - begin + 1).fill(0)
let now = begin
for(let i = 0; i < result.length; i++) {
result[i] = findBiggestNum(now)
now++
}
return result
}
const findBiggestNum = (num) => {
let result = 0
for(let i = 2; i <= Math.sqrt(num); i++) {
if(num % i === 0) {
if(num / i > 10000000) continue
return num / i
}
}
if(num === 1) return 0
else return 1
}코드 풀이
가장 먼저 반환해 줄 배열을 만들고 안의 값은 0으로 만들어준다.
배열의 크기만큼 반복을 실시한다. 선언부의 변수는 배열에 사용되기 때문에 0부터 시작해준다. 반복문의 내부에는 만들어준 함수를 실행하도록 한다.
새로 선언한 함수의 내부에서는 위의 규칙처럼 자신을 제외한 최대 약수를 구하는데 반복문의 시작은 2부터 시작하고 제곱근의 값까지 반복을 진행한다.
여기서 나머지 값이 0이 되더라도 블록의 종류는 10,000,000까지 나올 수 있기 때문에 최대 약수가 10,000,000을 넘어가게 된다면 그 최대 약수는 사용할 수 없는 값이기 때문에 continue를 통해서 넘어가도록 코드를 작성한다.
함수의 가장 아래에는 찾는 블록이 1번 블록이라면 0을 반환하도록 해준다.
해당 코드를 함수의 가장 아래에 작성한 이유는 최상단에 예외를 적용해서 적을 경우에 함수가 실행될 때마다 조건문이 실행되기 때문에 최하단에 return을 해주기 전에 예외를 적용하도록 한다.
반복문에서 최대 약수를 찾으면 바로 그 값이 반환되는 것으로 함수가 종료되기 때문에 찾지 못한다면 반복문을 빠져나와 블럭 번호를 가지고 판별한 뒤에 0 혹은 1을 반환하도록 한다.
