[java] 백준 2501번 약수 구하기

문제 요약

1. 자연수 N과 K가 주어졌을 때, N의 약수 중 K번째로 작은 수 출력
2. N의 약수의 개수가 K보다 적어서 K번째 약수가 없을 경우 0 출력

예제 입/출력 1을 보자.

6과 3이 주어졌다면 6의 약수는 1, 2, 3, 6이다. 3번째로 작은 수는 3이 출력된다.

 

예제 입/출력 2를 보자.

25와 4가 주어졌는데 25의 약수는 1, 5, 25이다. 4번째로 작은 수가 없으므로 0이 출력된다.

 

예제 입/출력 3을 보자.

2735와 1이 주어졌는데 2735의 약수는 1, 5, 547, 2735이다. 1번째로 작은 수는 1이 출력된다.

문제 풀이

1. 일단 자연수 N을 입력받아서 배열을 N만큼 선언 및 초기화한다.
2. 배열 arr에 N을 i(1~N)까지 나눠서 나머지가 0이면 i값을 넣어준다. (N=6일 때) arr = [1, 2, 3, 0, 0, 6] 이 된다.
3. 다른 배열 count를 하나 선언해주고 2번의 배열에서 0이 아닌 값만 넣어주도록 한다.
4. 해당 K번째 작은 수를 count[K-1] 로 리턴 시켜주면 끝. (배열은 index가 0부터 시작)

 

코드를 보면

n_count라는 변수로 N을 나눈 나머지가 0일 때만 개수를 세서 N의 약수만을 담은 배열 count의 크기를 정해주었다.

 

중요한 부분은 공책에서 끄적였던 것과 문제 풀이를 보면 풀 수 있다!

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(divisor(N,K));
    }

    public static int divisor(int N, int K){
        int[] arr = new int[N];

        int n_count=0;
        for(int i=0; i<N; i++){
            if (N % (i+1) == 0){
                arr[i] = i+1;
                n_count++;
            }
        }
        if(n_count < K)
            return 0;
        int[] count = new int[n_count];
        int j=0;
        for(int i : arr){
            if(i != 0){
                count[j] = i;
                j++;
            }
        }


        return count[K-1];
    }
}