[2501] 약수 구하기

난이도: ★★☆☆☆ • solved on: 2025-07-12

---

문제 요약

• 문제 유형: 구현, 브루트포스
• 요구사항:
  • 자연수 $n$과 $k$가 주어질 때,
    $n$의 약수들 중 $k$번째로 작은 수를 출력해야 한다.
  • 만약 $k$번째 약수가 존재하지 않으면 0을 출력.

---

사용 개념

1. 자료구조

   • 배열(ArrayList 등) (개선 방법에서 사용)

2. 알고리즘/기법

   • 단순 반복문(1부터 n까지)
   • 약수 구하기

3. 핵심 키워드

   • 약수(divisor)
   • $k$번째

---

풀이 아이디어 및 코드

방법 1 : 브루트포스 (1부터 $n$까지 반복)

1. 문제 분해
   • 1부터 n까지 차례로 모든 수 $i$에 대해 $n$이 $i$로 나누어떨어지는지 확인 → 약수 찾기
   • 찾을 때마다 카운트 증가, $k$번째면 바로 출력
2. 핵심 로직 흐름

   for i = 1 ~ n:
       if n % i == 0:
           cnt++
           if cnt == k:
               print i
               종료

3. 예외 처리
   • 반복문이 끝난 후에도 cnt < k → 0 출력

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);
        int cnt = 0;
        for(int i=1;i<=n;i++){
            if(k==1){
                System.out.print(1);
                cnt++;
                break;
            }
            if(n%i==0){
                cnt++;
                if(cnt==k){
                    System.out.print(i);
                    break;
                }
            }
        }
        if(cnt<k){
            System.out.print(0);
        }
    }
}

---

방법 2 : 약수는 짝으로 존재함을 이용

1. 문제 분해

• 약수는 항상 $i$와 $n/i$의 짝으로 등장 (i* (n/i) = n)
• 1~√n까지만 반복, 약수를 리스트에 저장
• 반복 종료 후 리스트를 정렬 → k번째 찾기 (공간, 시간 모두 개선)

2. 핵심 로직 흐름

   for i = 1 ~ sqrt(n):
       if n % i == 0:
           add i
           if i != n/i: add n/i
   정렬
   k-1 인덱스 값 출력 (없으면 0)

3. 예외 처리
   • k > 약수 개수면 0

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        ArrayList<Integer> divisors = new ArrayList<>();
        for(int i = 1; i * i <= n; i++) {
            if(n % i == 0) {
                divisors.add(i);
                if(i != n / i) divisors.add(n / i);
            }
        }
        Collections.sort(divisors);

        if(k > divisors.size()) System.out.println(0);
        else System.out.println(divisors.get(k - 1));
    }
}

---

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

방법 2

• 시간 복잡도: O(√N + D log D) (D: 약수 개수, 보통 O(√N))
• 공간 복잡도: O(D) (약수 저장)

---

어려웠던 점

• 1부터 n까지 점검하는 경우 브루트포스 (brute force) 방식이라 매우 직관적이지만, n의 범위가 커질 경우 시간 초과가 될 수도 있다.
• 약수는 항상 짝을 이루는 성질을 활용하면 더 빠른 풀이가 가능하다는 점을 처음에는 떠올리기 어려웠다.

---

배운 점 및 팁

• 약수 문제는 1~$n$ 반복보다는 1~√$n$까지만 검사하고 짝을 활용하는 습관을 들이면 시간 절약이 크다.
• 입력이 큰 경우, ArrayList에 약수 저장 후 정렬로 $k$번째 값을 바로 찾을 수 있다.
• 브루트포스 (brute force) 도 $n$이 크지 않다면 무난히 사용할 수 있다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2501
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • [1978] 소수 찾기
  • [2581] 소수
  • [1037] 약수

• 확장 문제 (GPT 추천):

  • k번째 소수 찾기
  • 약수의 합 구하기
  • 약수의 개수 구하기