[프로그래머스] LV.4 숫자 블록 (JS)

문제

그렙시에는 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 함수를 완성해 주세요.

제한

• begin, end 는 1 이상 1,000,000,000이하의 자연수 이고, begin는 항상 end보다 작습니다.
• end - begin 의 값은 항상 10,000을 넘지 않습니다.
  

입출력 예시

begin	end	result
1	10	[0, 1, 1, 2, 1, 3, 1, 4, 3, 5]

풀이

다른 Lv.4 난이도의 문제와 비교했을 때 그렇게 어렵지 않게 풀 수 있는 문제인 것 같다. 시작점 begin과 종료점 end가 주어지기 때문에 구간에 대한 설치 블록을 파악해야 한다. 이때 지점은 최대 1,000,000,000의 크기이기 때문에 주어진 시간 안에 통과할 수 있도록 효율적인 작업이 필요할 것 같아 보인다. 하나씩 차근차근 풀어보도록 하자.

1) 블록 배열 규칙

문제를 읽어보면 블록은 1번부터 시작해서 최대 10,000,000번까지 배치할 수 있다. 이때 블록의 번호를 n이라고 하자. 각 n번 블록은 시작지점부터 종료지점까지 n * 2, n * 3, n * 4, ... 위치마다 배치된다. 그리고 만약 새로운 블록이 배치되는 경우엔 기존에 배치된 블록을 대체하도록 한다. begin = 1, end=10으로 주어졌을때 표로 나타내면 다음과 같다. 굵은 글씨가 새롭게 배치된 블록을 의미한다.

	1	2	3	4	5	6	7	8	9	10
1번	0	1	1	1	1	1	1	1	1	1
2번	0	1	1	2	1	2	1	2	1	2
3번	0	1	1	2	3	1	1	3	1	1
4번	0	1	1	2	3	1	1	4	1	1
5번	0	1	1	2	3	1	1	4	1	5

해당 로직을 그대로 구현한다면 1번 블록부터 마지막 블록 10,000,000번까지 반복문을 돌며 주어진 범위 내에 배치 가능한 칸을 앞에서 부터 채워나가야 할 것이다. 하지만 구간의 최대 거리는 1,000,000,000이고 블록 역시 10,000,000번까지 반복해야 하니 당연히 어마어마한 시간소요가 걸린다. 때문에 블록을 앞에서부터 배치하면서 계산하는 방식은 절대 불가능하다.

하지만 표를 자세히 살펴보자. 굵은 글씨로 표시한 부분은 다음 블록에 의해 새롭게 대체된 블록을 의미한다. 1번 블록의 경우에는 첫 번째 블록을 제외한 나머지 모든 블록이 1로 대체되었다. 두 번째 블록의 경우는 4번과 8번 블록이 2로 대체되었다. 세 번째 블록은 6번과 9번, 네 번째는 8번 그리고 다섯 번째 블록은 10번 블록이 대체되어 최종적으로 [0, 1, 1, 2, 1, 3, 1, 4, 3, 5]가 정답이 되는 것을 알 수 있다.

배치 규칙을 한 마디로 정리하면 자기자신을 제외한 배수에 해당하는 칸에 배치하는 것과 같다. 위에서 나온 결과가 그것을 증명한다. 몇 번 블록까지 진행해야 할 지는 주어지는 구간에 따라 달라지게 되지만, 사실 몇 번 블록까지 진행되는지를 굳이 파악할 필요가 없다. 왜냐하면 각 번호의 배수마다 블록이 배치된다면 최종적으로 마지막에 배치된 블록의 넘버는 결국 각 지점의 약수 목록 중에 자기 자신을 제외한 최대 약수가 되기 때문이다. 자기 자신을 제외하는 이유는 배치 규칙에 의해 애초에 블록 넘버에 해당하는 위치에는 해당 블록을 배치하지 않기 때문이다.

즉 우리는 다음의 핵심 규칙을 알 수 있다.

• 주어진 구간에서 각 지점을 X1, X2, X3, ... Xn 이라고 하자
• 이때 X1에 배치할 수 있는 가장 큰 블록의 넘버를 구해야 한다.
• 이는 X1의 약수 중에서 자기 자신을 제외한 가장 큰 약수이다.
• 나머지 X2, X3, ..., Xn 역시 모두 동일하다.

2) 약수 구하기

위의 규칙을 통해 우리는 모든 블록을 1씩 증가시키면서 각각의 경우를 구해줄 필요가 없다는 사실을 깨달았다. 즉 한 번의 반복문으로 주어진 begin 부터 end 까지 순회하면서 각 지점의 약수를 구해 자신을 제외한 최대값을 리턴해주도록 해주면 될 것 이다.

이때 약수를 구하는 것 역시 반복문을 통해 구하게 된다. 각 지점의 최대값이 매우 큰 값이기 때문에 이 과정에서 별도로 최적화를 하지 않는다면 시간 초과에 걸릴 우려가 있다. 따라서 우리는 약수를 구하는 과정에서 최적화를 적용할 필요가 있다.

약수를 빠르고 효율적으로 구할 수 있는 알고리즘은 다양하다. 해당 포스트에서는 적당히 빠르고 이해하기도 쉬운 방법을 통해 최적화를 진행하겠다. 단순히 빠르기로만 따지면 이 보다 빠른 방법도 존재한다.

먼저 약수의 정의는 자신과 나누어 떨어지는 수의 집합이다. 즉 모든 정수는 1과 자기 자신을 약수로 가진다. 따라서 우리는 2부터 자기 자신보다 1만큼 작은 수까지 반복하여 나누어떨어지는 지 체크하면 약수의 목록을 구할 수 있을 것이다. 그렇지만 우리는 약수로 나오는 값의 성질을 이용하면 굳이 자기 자신보다 1만큼 작은 수까지 반복할 필요가 없다는 것을 알 수 있다.

예를 들어 10의 약수를 구하는 과정을 살펴보자. 10의 약수는 총 4개로 [1, 2, 5, 10]과 같다. 정석대로라면 2부터 9까지 10과 나누어 떨어지는지 체크하여 나누어 떨어지는 2와 5에 1과 자기 자신 10을 합하여 위 결과를 얻을 수 있을 것이다.

하지만 약수가 짝수 개 있을 때는 처음과 끝을 하니씩 좁히면 서 두개씩 곱하면 자기자신이 되는 것을 알 수 있다. 만약 홀수 개라면 가운데 위치한 값을 제외하고 이 같은 법칙이 동일하게 성립함을 알 수 있다. 그리고 가운데 위치한 약수는 제곱을 통해 자기자신의 값을 만들 수 있다. 이처럼 약수의 집합에서 약수끼리는 서로 곱을 통해 원래의 수를 만들어 줄 수 있다.

따라서 우리는 모든 약수를 N-1까지 반복하며 구해주는 것이 아니라 sqrt(N)까지만 구해줌으로써 시간을 단축할 수 있다. 즉 N의 제곱근보다 작거나 같은 값까지 약수를 구해주는 것이다. 나머지 약수는 이미 구한 약수와 N을 나누어 줌으로써 그 반대편에 위치한 약수 목록을 구할 수 있다. sqrt(N)까지만 구해도 성립하는 이유는, 두 수의 곱으로 구할 수 있는 N의 최대값이 제곱근이 되기 때문이다. 두 수의 곱으로 원래 값 N을 만들 수 있다면 두 수 모두 약수이기 때문에, 두 수 중에서 짝을 이루는 하나의 값만 먼저 구하고 나머지는 원래값 N과의 나눗셈을 통해 구해주는 것이다.

따라서 반복의 횟수를 sqrt(N)까지 줄일 수 있다. 하지만 여기서 우리는 또 하나의 최적화를 할 수 있다. 우리가 구해야 하는 값은 모든 약수 목록이 아니기 때문이다. 우리가 구해야 하는 값은 1과 자기자신을 제외한 약수 중 가장 큰 값이라는 점을 잊지 말자.

따라서 이에 해당하는 약수는 1을 제외하고, sqrt(N)까지 반복하면서 가장 먼저 나누어 떨어지는 i 값으로 N을 다시 나눈 값이 될 것이다. 이때 블록의 넘버는 10,000,000번까지 있다는 점에 유의하자. 이를 초과하는 경우에는 블록을 배치할 수 없기 때문에 첫 번째 지점을 제외한 모든 지점에 배치할 수 있는 1번 블록이 자리잡고 있을 것이다.

위에서 설명한 내용을 바탕으로 약수를 구하는 함수를 구현하자.

const getMaxDivisor = (n) => {
  // 1을 제외하기 때문에 2부터 시작하여
  // n의 제곱근 까지 반복하며 값을 찾는다
  for (let i = 2; i <= Math.sqrt(n); i++) {
    // 가장 먼저 나누어 떨어지는 제일 작은 약수를 찾자
    // 이때 블록의 최대값을 초과하지 않아야 한다
    if ( n % i === 0 && n / i <= 1e7 ) {
      // 나누어 떨어지는 가장 작은 약수 (1 제외)를 구했다면
      // 원래의 값에서 이 약수를 나누어 준 몫이 제일 큰 약수
      return n / i;
    }
  }
  // 그런 약수를 찾지 못했다면 1을 반환한다
  // 1번 블록은 첫 번째 위치를 제외하고 모두 배치가 가능하기 때문
  return 1;
}

3) 구간에 해당하는 블록 배치 목록

위에서 구현한 getMaxDivisor 함수를 가지고 주어진 구간 내에 배치된 블록 현황을 구해주도록 하자. 이는 단순히 begin부터 end 까지 반복하며 각 지점의 값을 getMaxDivisor 함수의 매개변수로 넘겨주어 구할 수 있다.

그전에 먼저 리턴할 배열 arr을 초기화해주자. 해당 배열의 크기는 end - begin + 1이 될 것이다. 초기화는 먼저 0으로 진행해주자. 사실 0이 아닌 어떤 수로 진행하더라도 상관없다.

// begin - end 구간 크기에 해당하는 배열 생성
const arr = new Array(end - begin + 1).fill(0);

그리고 반복을 통해 1과 자시자신을 제외한 가장 작은 약수를 넣어주자. begin이 항상 1부터 시작하는 것이 아니기 때문에 위에서 생성한 arr 배열의 가장 처음부터 원소값을 넣어주기 위해서는 [i-begin]의 인덱스로 접근하면 된다.

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

마지막으로 주의해야 할 것은 1번 블록이라고 할 지라고 첫 번째 지점에는 블록 설치가 불가능한 것을 고려해주어야 한다는 점이다. begin=1인 경우에는 getMaxDivisor 함수에서 1을 반환하기 때문에 별도로 begin=1인 경우를 체크해서 arr[0] = 0으로 만들어주자.

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

4) 전체코드

약수와 정답의 상관관계를 잘 파악했다면 쉽게 풀 수 있는 문제였던 것 같다. 주석을 제외한 전체 코드는 다음과 같다.

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;
}

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

출처

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