숫자블록

블록을 하나씩 깐다. 그러나 나중에 블록이 깔리면 그 이전에 깔았던 블록을 덮어씌어 버린다.

그림으로 나타내면 아래와 같다.

규칙이 보이는가? 각 index에 놓일 숫자는 index의 약수중 가장 큰 약수를 구하면 된다.

약수중에 최대 약수는? 약수를 구한다음 그 약수로 본래의 숫자를 나누면 된다.

10의 약수를 구해보자. 1부터 하나씩 올라가면서 looping하면된다. 그럼 바로 2에서 걸릴 것이다. 10을 2로 나누면 5가 된다. 5가 10의 약수중 최대숫자가 된다.

그리고 하나씩 올라갈때 10까지 갈 필요없다. 제곱근에서 멈추면 된다.

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

그리고 이 최대약수를 각각의 index에 할당하자!

function solution(begin, end) {
  const arr = new Array(end - begin + 1).fill(0);

  for (let i = begin; i <= end; i++) {
    arr[i - begin] = getMaxDivisor(i);
  }

  if (begin === 1) arr[0] = 0;

  return arr;
}

알고리즘을 푸는게 중요한게 아니다. 알고리즘을 잘푸는 사람은 어떤식으로 접근하는지 아는게 중요하다. 법칙을 찾아내는게 중요하다.

그 법칙을 간단하게 정리해보았다.

1. 핵심은 전개되는 과정을 그림이나 표로 나타내기!(위의 표 그림 참고)
2. 그리고 시각화된 과정을 보고 반복되는 패턴을 찾기(index의 약수중 가장 큰 약수가 insert된다)
3. 그 패턴을 공식화 하는 방법을 알아내기!(getMaxDivisor)

위의 풀이방법도 위와 같은 법칙을 따라간다. 반복되는 패턴을 수식으로 나타내는 것이다. 결국 그 수식은 코드로 표현 가능하다.

이런 접근방식으로 알고리즘 문제를 접근해보자.

출처 :https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.4-%EC%88%AB%EC%9E%90-%EB%B8%94%EB%A1%9D-JS