백준 2501번

백준 2501번을 풀어보았다.

 

약수를 구하는 간단한 문제로, 크게 두 가지 풀이로 구분할 수 있다.

• 1부터 N까지 확인해보기
• 1부터 N의 제곱근까지 확인해보기

 

1부터 N까지 확인해보기

let [N, K] = require('fs').readFileSync('/dev/stdin').toString().split(' ').map(Number)

let cnt = 0, output = 0

for (let i = 1; i <= N; i++) {
  if (N % i === 0) cnt++
  if (cnt === K) {
    output = i
    break
  }
}

console.log(output)

 

위 코드에선 K번째가 되면 반복을 종료하고 바로 정답을 출력하도록 했지만

 

반복을 끝까지 수행하여 모든 약수를 배열에 저장한 뒤 K-1번째 요소를 출력할 수도 있다.

 

1부터 N의 제곱근까지 확인해보기

let [N, K] = require('fs').readFileSync('/dev/stdin').toString().split(' ').map(Number)

let divisors = []

for (let i = 0; i <= Math.sqrt(N); i++) {
  if (N % i === 0) {
    divisors.push(i)

    if (i * i !== N) {
      divisors.push(N/i)
    }
  }
}

divisors.sort((a, b) => a - b)

divisors[K-1] !== undefined ? console.log(divisors[K-1]) : console.log(0)

 

약수는 대칭적으로 존재하므로 i가 N의 약수이면 N/i도 N의 약수이다.

 

다만 i가 N의 제곱근일 경우 i와 N/i는 동일하므로 이 경우만 따로 처리해준다.

 

또한 반복문 종료 후 divisors는 [1, 6, 2, 3]과 같은 형태일 것이므로 K번째 약수를 출력하기 위해 divisors를 정렬해주어야 한다.

 

참고) 백준 10818번 - sort 메소드

 

💫 이 문제를 통해 배운 것

• 약수는 대칭적으로 존재하므로 N의 제곱근까지 반복하고도 모든 약수를 구할 수 있다.