🥉 [Baekjoon / Java] 2501. 약수 구하기

문제 설명

---

💡 Info

• 난이도 : 브론즈 III
• 시간 제한 : 1초
• 메모리 제한 : 128MB
• 백준 링크: https://www.acmicpc.net/problem/2501
• 풀이 링크(GitHub): hayannn/CodingTest_Java/백준/Bronze/2501.약수구하기

내용

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.

6을 예로 들면

• 6 ÷ 1 = 6 … 0
• 6 ÷ 2 = 3 … 0
• 6 ÷ 3 = 2 … 0
• 6 ÷ 4 = 1 … 2
• 6 ÷ 5 = 1 … 1
• 6 ÷ 6 = 1 … 0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

📥입력 조건

• 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

📤출력 조건

• 첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

입출력 예시

• 입력 1

  6 3

• 출력 1

  3

• 입력 2

  25 4

• 출력 2

  0

• 입력 3

  2735 1

• 출력 3

  1

유의 사항 및 제약 조건

---

.

문제 이해

---

• N의 약수들 중 K번째로 작은 수를 출력하기

알고리즘

---

실제 풀이 시간 : 20분

• N 입력받기
• K 입력받기
• N의 약수 구하기
  • N % i == 0를 만족하는 수만 나오도록 하기
  • 그 다음, 오름차순으로 정렬하기
• 수 비교하기: 위에서 고른 N의 약수 중 K번째에 있는 수를 출력하기

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();

        int arr[] = new int[100001];

        for(int i=1; i<N; i++) {
            while (N % i == 0) {
                arr[i] = N;
            }
            Arrays.sort(arr);
        }
        System.out.println(arr[K-1]);
    }
}

오답 체크

---

• 입력을 마쳤음에도 계속해서 입력을 받는 문제 발생

  • arr를 int형에서 → ArrayList로 변경하기

  • N의 약수를 찾는 부분에서 → arr.add(i)로 약수로 선정된 수 저장하기

  • Arrays.sort를 → Collection.sort로 변경하기

  • K번째 수를 바로 K-1로 구하던 조건을 → K ≤ arr.size()로 추가해서 구하기

    //before
    int N = sc.nextInt();
    int K = sc.nextInt();
    
    int arr[] = new int[100001];
    
    for(int i=1; i<N; i++) {
        while (N % i == 0) {
            arr[i] = N;
        }
        Arrays.sort(arr);
    }
    System.out.println(arr[K-1]);
    }

    //after
    int N = sc.nextInt();
    int K = sc.nextInt();
    
    List<Integer> arr = new ArrayList<>();
    
    for(int i=1; i<=N; i++) {
        if (N % i == 0) {
            arr.add(i);
        }
    }
    Collections.sort(arr);
    
    if(K <= arr.size()) {
        System.out.println(arr.get(K-1));
    } else {
        System.out.println(0);
    }
    }

최종 풀이

---

실제 풀이 시간 : 37분(첫 풀이 시간 포함)

• N 입력받기
• K 입력받기
• N의 약수 구하기
  • N % i == 0를 만족하는 수만 나오도록 하기
  • 그 다음, 오름차순으로 정렬하기
• 수 비교하기: 위에서 고른 N의 약수 중 K번째에 있는 수를 출력하기
  • K번째 수 조건 : K ≤ arr.size()

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();

        List<Integer> arr = new ArrayList<>();

        for(int i=1; i<=N; i++) {
            if (N % i == 0) {
                arr.add(i);
            }
        }
        Collections.sort(arr);

        if(K <= arr.size()) {
            System.out.println(arr.get(K-1));
        } else {
            System.out.println(0);
        }
    }
}