[프로그래머스] 숫자 블록

문제

숫자 블록

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

 

 

풀이

설명

구간에 깔려 있는 블록들의 숫자를 구하는 문제입니다.

 

블록 숫자 n값을 1부터 마지막 값까지 증가시키면서 구간 내 위치에 설치합니다.

n이 쓰여진 블록은 n * 2, n * 3, n * 4 번째 위치에 설치됩니다. 

 

다음 두 가지 값을 적절하게 선택하는 게 중요합니다.

• n의 최댓값
• n이 쓰여진 첫 번째 블록 인덱스

 

문제에서 제시한 n의 최댓값은 10,000,000이므로, 마지막 블록 인덱스를 2로 나눈 값과 비교해 더 작은 값을 선택합니다.

n이 쓰여진 첫 번째 블록 인덱스는 begin 이상이면서 n의 배수 중 최솟값을 선택합니다.

 

예시 코드

function solution(begin, end) {
  const blocks = Array(end - begin + 1).fill(0);
  const maxN = Math.min(Math.floor(end / 2), 10000000);

  for (let n = 1; n <= maxN; n++) {
    // begin 이상이면서 n의 배수 중 최솟값
    let i = Math.max(n * 2, begin + ((n - (begin % n)) % n));

    for (i; i <= end; i += n) {
      blocks[i - begin] = n;
    }
  }

  return blocks;
}