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

KG·2021년 5월 27일

알고리즘

목록 보기

51/61

문제

그렙시에는 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 난이도 문제와 비교하여 비교적 쉽게 접근했던 것 같다. 문제에서 요구하는 블록의 숫자 값이, 해당 블록에서 1과 자기자신을 제외한 최대공약수라는 점을 캐치하면 쉽게 풀 수 있다.

1) 최대공약수

문제의 예시를 살펴보자. begin은 1 이고, end는 10으로 주어졌다. begin 부터 end 까지 오름차순으로 순회하며 각각의 넘버의 최대공약수를 찾아보자. 이때 주의할 것은 1과 자기자신은 제외해야 한다는 점이다.

1: 공약수 - 1 / 최대공약수 - 0 (자기자신 제외)
2: 공약수 - 1, 2 / 최대공약수 - 1 (자기자신 제외)
3: 공약수 - 1, 3 / 최대공약수 - 1 (자기자신 제외)
4: 공약수 - 1, 2, 4 / 최대공약수 - 2
5: 공약수 - 1, 5 / 최대공약수 - 1 (자기자신 제외)
6: 공약수 - 1, 2, 3, 6 / 최대공약수 - 3
7: 공약수 - 1, 7 / 최대공약수 - 1 (자기자신 제외)
8: 공약수 - 1, 2, 4, 8 / 최대공약수 - 4
9: 공약수 - 1, 3, 9 / 최대공약수 - 3
10: 공약수 - 1, 2, 5, 10 / 최대공약수 - 5

이때 1은 공약수가 오직 자기자신 밖에 없기 때문에 스스로를 제외하면 0이 된다는 점을 주의하자. 오른쪽에 최대공약수로 정리한 결과값이 결국 문제에서 요구하는 정답과 일치한다는 것을 알 수 있다. 즉 문제에서 요구하고 있는 n*2, n*3, n*4, n*5, ...의 흐름을 1씩 증가하는 n에 대입하면 각 단계마다 자신을 제외한 모든 배수를 체크하게 되고, 공배수의 경우는 가장 마지막에 접근한 n의 값으로 갱신되기 때문에 위와 같은 규칙이 성립한다.

제한 사항에 따르면 end - begin의 값은 항상 10,000을 넘지 않는다고 명시되어 있다. 따라서 처음부터 끝까지 순회하는 반복문 횟수는 최대 10,000회를 넘지 않을 것이다. 그러나 내부적으로 자신을 제외한 최대공약수를 구해야 하기 때문에 이 부분을 최적화해야 시간복잡도를 통과할 것이다. 따라서 나를 제외한 최대공약수를 빠르게 찾아낼 수 있도록 최적화를 적용해보자.

2) 자신을 제외한 최대공약수

최대공약수를 구하는 알고리즘은 다양하고, 이미 최적화가 이루어진 알고리즘 역시 존재한다. 아마 가장 대표적인 방법은 유클리드 호제법을 꼽을 수 있을텐데, 이 방식은 주어진 두 개 사이의 수에서 O(logN)의 시간복잡도로 최대공약수를 찾아내는 방식이다. 따라서 우리 문제에서는 이를 그대로 적용하기엔 다소 적절하지 않다.

물론 이를 응용 및 변형하여 구할 수 있겠지만, 사실 문제에서 요구하는 제한사항이 그렇게까지 빡빡하지 않기 때문에 또 다른 최적화 방식을 이용해서 자신을 제외한 최대공약수 값을 구해보도록 하자.

이는 소수(Prime Number)를 구할 때도 사용하는 방식인데 바로 제곱근을 이용하는 방식이다. N이 있을 때, N의 약수는 무조건 Sqrt(N) 범위 내에 존재하는 것이 성립한다. 만약 N = 12일 때, 이의 제곱근은 약 3.46이고 약수는 1, 2, 3, 4, 6, 12가 존재한다. 여기서 1과 12를 제외했을 때 나머지는 2*6, 3*4, 4*3, 6*2의 결과로 구성이 가능하다는 것을 알 수 있다. 즉 이들 관계는 몫이 커지면 나누는 값이 작아지거나 나누는 값이 커지면 몫이 작아지는 반비례 관계이다. 결국 N의 절반인 제곱근까지 도달하면 이후의 관계는 몫과 나누는 값이 작아지는 관계가 성립하기 때문에 그 이후를 계산해 줄 필요가 없다. 더 자세한 수학적 증명은 다른 게시글을 참고하자.

따라서 begin 부터 end까지 1씩 증가하는 n값을 넘겨받아 sqrt(n)까지 반복하며 약수를 찾아주도록 하자. 여기서 우리가 원하는 값은 자기자신을 제외한 최대공약수인데, 때문에 더 빠르게 원하는 값에 접근할 수가 있다.

일단 1의 경우는 항상 자기자신만을 공약수로 가지기 때문에 제외하자. 따라서 i = 2부터 시작하여 sqrt(n)까지 반복을 하게 될 것이다. 앞서서 약수의 관계를 살펴볼 때 몫 * 나누는 값 = n이 성립하는 것을 보았다. 여기서 몫이 2부터 시작하는데, 이는 최소값이므로 만약 n이 2로 나누어떨어진다면 나누는 값이 자연스레 자신을 제외한 가장 큰 공약수가 될 것이다. 따라서 반복문의 앞에서부터 나누어떨어지는지를 체크한다면 나누어 떨어지는 그 순간의 값이 바로 우리가 구하고자 하는 최대 공약수가 된다는 것을 알 수 있다!

이때 한 가지를 더 주의하자. 제한 사항에 의하면 블록의 숫자는 10,000,000까지 가능하다. 이 부분이 약간 헷갈렸는데 10,000,000이 넘어가는 숫자는 다시 처음으로 되돌아오는 것인지, 아니면 아예 사용을 하지 않는 것인지 명확하지 않았다. 결론부터 말하자면 후자이다. 10,000,000이 넘어가는 경우에는 더 이상 사용할 블럭이 없기 때문에 1을 리턴하도록 구현하면 된다. 여기서 10,000,000의 숫자 블록이 의미하는 것은 항상 주어진 n값을 i로 나눈 몫이라는 점에 유의하자!

const getDivisorts = (n) => {
  // 2부터 sqrt(n)까지 반복문을 순회하도록 최적화
  for(let i = 2; i <= Math.sqrt(n); i++) {
    // n이 i로 나누어떨어지는 순간 이들 간의 반비례 관계에 의해
    // 이때의 몫(n / i)가 곧 자신을 제외한 최대공약수가 된다
    // 다만 몫이 10000000 넘는 경우는 제외해야 한다
    if(n % i === 0 && n / i <= 1e7) {
      return n / i;
    }
  }
  // 만약 위에서 최대공약수를 찾지 못했다면
  // 1과 자시자신만 공약수로 갖고 있는 수가 되기 때문에
  // 자신을 제외한 1을 리턴하도록 하자
  return 1;
}

3) 블록 설치

위에서 구현한 getDivisors 함수를 이용하여 정답을 구해보자. 먼저 리턴하는 배열 arr의 길이는 end - begin + 1의 크기가 될 것이다. 초기값은 모두 0으로 하여 초기화 해주자.

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

그리고 앞서 말했듯이 begin 부터 end 까지 반복문을 돌며 arr의 처음부터 현재 i값의 자신을 제외한 최대공약수를 구해주도록 하자.

for(let i = begin; i <= end; i++) {
  // begin 값이 항상 0이 아닐 수 있으므로
  // 인덱스를 0으로 재조정해주자
  arr[i - begin] = getDivisors(i);
}

이때 한 가지 또 주의해야 할 점이 있다. 바로 1은 자기자신을 제외하고는 공약수를 가지지 않는다는 점이다. 때문에 1의 경우에는 항상 0번 블록을 매길 수 밖에 없다. 이 부분을 체크해주도록 하자.

// begin이 1인 경우를 체크하여 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] = getDivisors(i);
  }
  
  if (begin === 1) arr[0] = 0;
  
  return arr;
}

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