BAEKJOON 2501번: 약수 구하기

2501번 문제

문제

입력

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

출력

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

🗝️포인트

처음 문제를 접하고 코드를 짰을 때에는 ArrayList를 이용하여 담은 뒤 해당 int 배열로 mapping 후 정답을 도출하였다.

하지만, 코드 제출 후 생각해보니 요구하는 결과를 도출할 때 굳이 모든 약수를 담을 필요는 없다는 생각을 했다.

따라서 아래와 같이 해당 약수의 갯수를 카운팅 할 cnt라는 변수를 선언하여 cnt가 K 값과 같을 경우, 해당 약수가 K번째 약수일 것이라 가정한 뒤 코드를 짜보았다.

결과는 통과했고 예상과 맞았다. 아직 논리 사고력이 부족하여 해당 결과가 정확하게 어떻게 출력될 것인지 바로 생각이 나지 않지만 차근차근 생각을 쌓아나가고 있는 중이다!

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
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()," ");

		Integer N = Integer.parseInt(st.nextToken());

		Integer K = Integer.parseInt(st.nextToken());

		int cnt = 0; // 약수의 갯수 카운팅

		int res = 0; // K번째 약수를 출력.

		for(int  i=1; i <= N; i++){
			
			if( N%i ==0) cnt++;

			if(cnt == K) {res = i; break;}
		}

		System.out.println(res);
		br.close();
	}
}