[BaekJoon] 2501번 - 약수 구하기 (java)

📌 1. 문제

👉 문제 바로가기

- 조건

시간 제한	메모리 제한
1초	128MB

- 문제

어떤 자연수 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을 출력하시오.

- 예제

입력	출력
6 3	3
25 4	0
2735 1	1

---

📌 2. 풀이

2-0. 알고리즘

1부터 N까지 루프를 돌며 약수를 찾아낸다.
i가 약수인 경우, 몇번째인지 구하기 위해 num을 1씩 추가한다.

num이 K와 같을 경우 i를 출력하고 for 문을 빠져나간다.

for(int i=1;i<=N;i++) {
    if(N % i == 0) {
        num++;
        
        if(num == K) {
            System.out.println(i);
            break;
        }
    }
}

루프를 끝내고 N의 약수의 개수가 K보다 적으면 0을 출력한다.

if(num < K) {
    System.out.println(0);
}

2개의 입력방식을 사용해서 결과를 출력한다.

1. Scanner 클래스
2. BufferedReader 클래스
   
   
   

2-1. Scanner 클래스

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();
        int num = 0;
        
        for(int i=1;i<=N;i++) {
        	if(N % i == 0) {
        		num++;
        		
        		if(num == K) {
        			System.out.println(i);
                                break;
        		}
        	}
        }
        if(num < K) {
        	System.out.println(0);
        }
    }
}

위와같이 객체를 생성할 때, Scanner(System.in) 에서 System.in 은 입력한 값을 Byte 단위로 읽는 것을 뜻한다.

int형 데이터를 입력받기 위해 nextInt() 메서드를 사용한다.

[여기서 잠깐!]

Scanner에 대해 더 자세히 알고싶다면 여기 를 클릭하세요

2-2. BufferedReader 클래스 사용

readLine() 메서드를 사용해 읽어온 문자열을 공백단위로 분리한다.
문자열 분리 방법으로는 StringTokenizer 클래스를 사용한다.

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int num = 0;
        
        for(int i=1;i<=N;i++) {
        	if(N % i == 0) {
        		num++;
        		
        		if(num == K) {
        			System.out.println(i);
                                break;
        		}
        	}
        }
        if(num < K) {
        	System.out.println(0);
        }
    }
}

readLine()은 한 줄을 통째로 읽어 String으로 반환하기 때문에, StringTokenizer 클래스의 nextToken()를 이용해 공백으로 구분된 입력값들을 순서대로 가져온다.

Integer.parseInt()을 사용해 String형을 int형으로 변환시켜준다.

[여기서 잠깐!]

BufferedWriter 클래스에 대해 더 알아보고 싶으면 여기를 클릭하면 된다.

---

3. 성능 비교

입력의 경우 확실히 Scanner 보다는 BufferedReader 가 빠른 것을 볼 수 있다.

관련 페이지

• Scanner 클래스
• BufferedReader/BufferedWriter 클래스