[BOJ] 2501번 : 약수 구하기

백준 2501번 : 약수 구하기

🔗 문제 링크

https://www.acmicpc.net/problem/2501

2501번: 약수 구하기

 

---

💬 문제

 약수 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

 

1. 자연수 N의 약수 중 K번째로 작은 약수를 구해 출력해준다.
   
   - 1번째 줄에 N과 K가 공백을 기준으로 주어진다
   
   

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 N과 K를 주고 있다. 공백을 기준으로 N과 K를 잘라주고 정수화해주면 된다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

💻 풀이

이 문제는 나누는 수의 범위와 약수를 찾는 방법에 따라 총 3가지 방식으로 풀 수 있다.

🔑 풀이1 : 모든 수로 나눠 약수 구하기

• 공백을 기준으로 잘라주고, N과 K를 정수화해준다.
  
  
• for문으로 2부터 N까지 모든 수로 N을 나눠 약수 배열 divisor을 채워준다.
  
  - 1은 항상 약수이므로, 미리 약수 배열 divisor에 넣어준다.
  
  
• K번째 약수가 존재하려면 배열의 길이는 K보다 크거나 같아야 한다.
  
  - K번째로 작은 약수를 출력해주거나, 0을 출력해준다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
[N, K] = input;

console.log(solution(N, K));

function solution(N, K) {
  const divisor = [1];  // 약수 (배열)
  for (let i=2; i <= N; i++) {
    if (N % i === 0) {  // 약수일 때
      divisor.push(i);
    }
  }
  if (divisor.length < K) {
    return 0;  // K번째 약수가 없을 경우 (K가 배열길이보다 클 때) 
  } else {
    return divisor[K-1];
  }
};

 

시간은 다음과 같이 걸렸다.

 

 

---

🔑 풀이2 : 제곱근 범위까지만 나눠 약수 구하기

• 공백을 기준으로 잘라주고, N과 K를 정수화해준다.
    
• for문으로 모든 수를 도는 것보다 제곱근까지 도는 것이 조금 더 효율적이다.
  
  -  Math.sqrt()  메서드로 제곱근을 구할 수 있다.
    
• i가 약수일 때, N을 i로 나눈 수도 약수이기에 동시에 배열 divisor에 추가해준다.
  
  - 제곱근이 약수와 같을 땐, 약수 하나만 추가해야 한다 (예시> 5 X 5)
    
• K번째 약수가 존재하려면 배열의 길이는 K보다 크거나 같아야 한다.
  
  - K번째로 작은 약수를 출력해주거나, 0을 출력해준다.
  - 약수 i의 상대값도 동시에 추가해줬기에 정렬해줘야 한다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
[N, K] = input;

console.log(solution(N, K));

function solution(N, K) {
  const divisor = [];
  for (let i=1; i <= Math.sqrt(N); i++) {  // 제곱근까지만 나눠주기
    if (i * i === N) {  // 약수 = 제곱근
      divisor.push(i);
    } else if (N % i === 0) {  // 약수일 때
      divisor.push(i);
      divisor.push(N / i);
    }
  }
  if (divisor.length < K) {
    return 0;  // K번째 약수가 없을 경우 (K가 배열길이보다 클 때) 
  } else {
    return divisor.sort((a,b) => a - b)[K-1];  // K번째 약수 출력
  }
};

 

제곱근까지만 for문을 돌렸기에 아주 약간 더 시간이 빨라졌다.

 

 

---

🔑 풀이3 : K의 값을 역산하여 K번째로 작은 약수 찾기

• 공백을 기준으로 잘라주고, N과 K를 정수화해준다.
    
• for문으로 1부터 N까지 모든 수로 N을 나눠주고, 약수가 있을 때마다 K의 값에서 1을 빼준다.
    
• K가 0이 되었을 때, 약수 i를 출력해준다.
  
  - K번째 약수가 없다면, 0을 출력해준다
  - K번째 약수가 없다면, K는 0이 되지 못한다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
[N, K] = input;

console.log(solution(N, K));

function solution(N, K) {
  for (let i=1; i <= N; i++) {
    if (N % i === 0) {  // 약수일 때 K-1
      K--;
    }
    if (K === 0) {  // K번째로 작은 약수
      return i;
    }
  }
  return 0;  // K번째 약수가 없을 경우 (K가 0이 되지 못했을 때)
};

 

시간은 다음과 같이 걸렸다.