📌 문제

[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을 출력하시오.

💡 코드

✅ n의 약수의 개수는 가변적이기 때문에, 크기가 가변적인 ArrayList에 약수를 저장한다. for문을 통해 n을 1 ~ n 까지의 숫자로 나눈 후, 나머지가 0인 경우에만 arr 에 추가. 연산을 1 ~ n 순서로 수행하기 때문에 arr은 가장 작은 수 ~ 가장 큰 수 의 정렬을 가짐. 따라서, k번째로 작은 수는 인덱스 k-1번에 위치한 수이다.

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		List<Integer> arr = new ArrayList<Integer>();
		
		for(int i=1;i<=n;i++) {
			if(n % i == 0) arr.add(i);
		}

		int result = 0;
		if(arr.size() >= k) result = arr.get(k-1);
		bw.write(result + "");
		
		br.close();
		bw.close();
	}
}

➕ 다른 사람의 코드 : 약수를 모두 구해서 따로 저장하지 않고, cnt를 사용하여 k번째 약수를 구했을 때 바로 실행을 종료시킴. 이 때, return문은 실행을 즉시 종료시키므로, bw.close()를 return 실행 전에 써줘야 제대로 출력이 된다!

import java.io.*;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int cnt = 0;
		
		for(int i=1;i<=n;i++) {
			if(n % i == 0) {
				cnt++;
				if(cnt == k) {
					bw.write(i + "");
					bw.close();
					return;
				} else {
					
				}
			}
		}
		bw.write("0");
		
		br.close();
		bw.close();
	}
}