2Level / 연습문제 / 숫자 블럭

문제 설명

 

제한 사항

 

문제 풀이 방법

• 이 문제에서 주의 해야할 부분은 우선 블럭이 2번째 블럭 부터 설치가 시작되고,
  총 길이가 1e9인 도로에서 1부터 10,000,000 까지의 숫자로 구성된 도로라는 것이다.
• 입출력 예를 보게되면 각 블럭 위치의 약수의 수가 해당 위치에 위치하게되는데,
  이 약수는 위에서 이야기한 1 부터 10,000,000 까지의 숫자로 구성되어야 한다.
• 약수를 구하는 함수를 만들 때 begin이 1인 경우는 첫번째 블럭에 0이 와야 하므로 if문으로 예외를 작성해주자.
  (1은 2번째 블럭부터 작성 가능하기에)
• 함수에 임의의 변수에 1을 할당해준다. 이는 블럭을 구성 하는 숫자들 중 소수인 위치에 1을 넣기 위함이다.
• 약수를 구할 때 효율과 속도를 높이기 위해 숫자의 제곱근 까지 for문을 돌려 약수를 구한다.
  제곱근을 이용해 약수를 구한다면 1부터 시작해 제곱근 까지의 약수를 구할 수 있을 뿐만 아니라
  반대편 약수도 구할 수 있기 때문이다.
• for문에서 숫자와 나머지가 0이되는 약수들을 찾았고 그 중 가장 큰 약수를 1을 할당했던 임의의 변수에
  재할당 해준다.
•  그 다음 숫자와 약수들 중 가장 큰 수를 나눈 값이 1e7 이하인 값은 나눈 결과 값을 반환해준다.
  이유는 해당 위치에 올 수 있는 가장 큰 약수, 즉 모든 블럭을 구성하는 숫자의 범위 내에 있는
  숫자를 블럭에 넣어야 하기 때문이다.
• 나눈 값이 1e7보다 크면 위에서 임의의 변수에 할당한 값을 반환해준다.
  이는 해당 약수를 제외한 약수는 소수인 경우이기 때문이다.
  ex) 6250001(소수) * 6 = 100000016
• 이제 약수를 구하는 함수를 이용해 for문으로 begin부터 end까지 반복해 배열을 구한 뒤 반환하면 된다.

 

내가 작성한 코드

const solution = (begin, end) => {
    let answer = [];

    for(let i=begin; i<=end; i++){
        answer.push(division(i));
    }
    return answer;
}

const division = (num) => {
    let a = 1;
    if(num === 1) return 0;
    for(let i=2; i<=Math.sqrt(num); i++){
        if(num%i === 0){
            a=i;
            if(num/i <= 1e7){
                return num/i;
            }
        }
    }
    return a;
}

 

 

 

이 문제는 결국 다른 사람들이 작성한 답을 참고해서 내가 이해하고

다시 작성한 코드를 작성했다.

 

내가 놓쳤던 부분은 우선 숫자의 구성이 1부터 10,000,000 까지라는 것과 절대값을 이용한 약수 구하기,

소수인 값에 1을 대입하는 것이다.

이 3개가 가장 핵심적인 것이라 생각한다.

 

1부터 10,000,000 까지의 숫자 구성은 약수의 범위를 설정해 제곱근 이하의 약수와 매칭되는 약수를 추가.

이것 개념을 보고 머리가 띵했다... 내가 너무 예시값을 작게만 생각했고,

숫자의 범위를 잘 안보고 넘어간 것에 대해 안일하게 문제를 풀었다 생각했다.

 

두번째로 절대값을 이용한 약수 구하기는 효율성을 높이기 위해 이용했다.

아무레도 for문으로 큰 수의 약수를 모두 구하려면 효율성 검사에 걸릴 것 같아 이용하게 되었다.

 

세번째로 소수인 위치에 1을 대입하는 것이다.사실 말로 하면 당연하다 생각한다. 하지만 그 방법이 나에게는 낮설었다.우선 변수에 1을 할당하고 1과 자신을 제외한 다른 약수를 발견하면 그 약수를 할당해 이용하는 것이다.이렇게 하면 조건문을 추가적으로 사용할 필요가 없어진 것이다.

 

 

나도 아직 많이 부족한것 같다.사실 이 문제가 Level2에서 정답률이 34%인 문제이지만 시간을 충분히 갖고 문제를 제대로 이해 했다면,풀 수 있었다고 생각하는 문제이다.하지만 내가 못풀었으니 내가 부족한 점을 파악하고 그 점을 보안하면 실력은 좋아질 것이다.

 

이번 문제로 문제의 조건을 제대로 파악하고, 약수를 구할때 제곱근을 이용하는 것과, 숫자가 소수인 경우와 조건에 맞는 약수를 구하는 로직을 배울 수 있었다.